题意：

思路：

https://ac.nowcoder.com/discuss/151522?type=101&order=0&pos=1&page=0&channel=666&source_id=discuss_tag

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
const int M = 1e6 + 10;
const int N = 1e3 + 10;
typedef long long ll;
const ll inf = 1e18;
struct Edge{
    int u,to,w,nex;
}e[M];
int head[N],idx;
int n,m;

void add_edge(int u,int v,int w){
    e[idx].u = u;
    e[idx].to = v;
    e[idx].w = w;
    e[idx].nex = head[u];
    head[u] = idx++;
}
ll dist[N];
bool in[N];
void spfa(int S){
    for(int i = 0;i <= n;i++){
        dist[i] = inf,in[i] = 0;
    }
    queue<int> q;
    dist[S] = 0;
    q.push(S);
    while(q.size()){
        int u = q.front();q.pop();
        in[u] = 0;
        for(int i = head[u];~i;i = e[i].nex){
            int v = e[i].to,w = e[i].w;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                if(!in[v]){
                    q.push(v);
                    in[v] = 1;
                }
            }
        }
    }
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i = 1,u,v,w;i <= m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
    }
    for(int i = 1;i <= n;i++) add_edge(0,i,0);
    spfa(0);
    for(int i = 0,u,v,w;i < m;i++){
        u = e[i].u,v = e[i].to,w = e[i].w;
        printf("%d %d %lld\n",u,v,dist[u] - dist[v] + w);
    }
    return 0;
}