#include<bits/stdc++.h>
#define pii pair<int,int>
#define MAXN 10010

using namespace std;

const int MOD = (int)1e9+7;

vector<pii> grafo[MAXN];

int dist[MAXN], pai[MAXN], rota[MAXN], min_vrota[MAXN], max_vrota[MAXN];
/*
rota[i]: nro de caminhos minimos para chegar no vértice i
min_vrota[i]: menor nro de vértices dentre as menores rotas até i
max_vrota[i]: maior nro de vértices dentre as menores rotas até i
*/

void dijkstra(int s){
    set<pii> q;
    q.insert({0,s});
    dist[s] = 0;
    rota[s] = 1;
    min_vrota[s] = 1;
    max_vrota[s] = 1;

    while(!q.empty()){
        int v = q.begin()->second;
        q.erase(q.begin());
        for(auto [w,u] : grafo[v]){
            if(dist[v]+w < dist[u]){
                q.erase({dist[u],u});
                dist[u] = dist[v]+w;
                q.insert({dist[u],u});
                pai[u] = v;

                rota[u] = rota[v];
                min_vrota[u] = min_vrota[v]+1;
                max_vrota[u] = max_vrota[v]+1;
            }else if(dist[v]+w == dist[u]){
                rota[u] += rota[v];
                rota[u] %= MOD;
                min_vrota[u] = min(min_volta[u],min_vrota[v]+1);
                max_vrota[u] = max(max_vrota[u],max_vrota[v]+1);
            }
        }
    }
}

int main(){
    int n, m; scanf("%d %d", &n, &m);

    for(int i = 0; i < m; i++){
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        grafo[a].push_back({c,b});
    }

    //
}