#include <bits/stdc++.h>

#define int long long
#define PII pair<int,int>
#define MP make_pair
#define INF LONG_LONG_MAX
using namespace std;
int n, m;
vector<PII > g[1510];//个人喜好用 vector 建图，但更推荐邻接表
int dis[1510];
bool vis[1510];

void spfa(int s) {
    queue<int> q;
    q.push(s);//把初始点加入队列
    fill(dis + 1, dis + 1 + n, INF);//因为一开始所有点都到不了，所以初始化为INF,不能设置为-INF!!!
    dis[s] = 0;//自己到自己肯定距离为0
    while (!q.empty()) {
        int u = q.front();//从队列里取出第一个元素
        q.pop();
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].first, w = g[u][i].second;
            if (dis[v] > dis[u] + w) {//松弛操作
                dis[v] = dis[u] + w;
                q.push(v);
            }
            //如果能松弛成功，那么松弛，把松弛成功的目标点放入队列
        }
    }
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u]....