Untitled

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second
// #define mod 1e9+7
#define mp make_pair
#define int long long

using ii=pair<int,int>;

int mod = 1e9+7;
int n,m;
int mpr=0;
vector<vector<ii>> g;
vector<int> vis,dis,cnt,mnd,mxd;


void dijkstra(){
    priority_queue<ii> p;
    
    p.push(mp(-0,1));
    int curp=-0;//current price
    int curn=1; // current node
    cnt[1]=1;
    
    while(!p.empty()){
        ii curs=p.top();
        p.pop();
        
        if(vis[curs.s]==1)continue;
        vis[curs.s]=1;
        //need to keep vis here 
        
        curn=curs.s;
        curp=-curs.f;
        
        for(auto v : g[curs.s]){
            if(dis[v.f]>curp+v.s){
                dis[v.f]=curp+v.s;
                p.push(mp(-dis[v.f],v.f));
                cnt[v.f]=cnt[curs.s];
                // cout<<cnt[v.f]<<" "<<v.f<<"\n";
                mnd[v.f]=mnd[curs.s]+1;
                mxd[v.f]=mxd[curs.s]+1;
            }
            
            /* As cost starts with 1, each edge 
            will be considered*/
            /* cnt will count same price edgess at each node*/
            
            else if(dis[v.f]==curp+v.s){
                (cnt[v.f]+=cnt[curs.s])%=mod;
                // cout<<cnt[v.f]<<" "<<v.f<<"\n";
                mnd[v.f] = min({mnd[v.f],mnd[curs.s]+1});
                mxd[v.f] = max({mxd[v.f],mxd[curs.s]+1});
            }
        }
    }
    
}

signed  main(){
    
    cin>>n>>m;
    
    g.resize(n+1);
    vis.assign(n+1,0);
    cnt.assign(n+1,0);
    mnd.assign(n+1,0);
    mxd.assign(n+1,0);
    dis.assign(n+1,1e15+10);
    
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a].push_back(mp(b,c));
    }
    
    dijkstra();
    
    // cout<<dis[n]<<" ";
    if(dis[n]!=1e15+10){
        cout<<dis[n]<<" "<<cnt[n]<<" "<<mnd[n]<<" "<<mxd[n]<<" ";
        
    }
    else cout<<"-1 ";
    
}