题意：
给你一个n个结点m条边的有负权边无负环的有向图，为每条边赋一个非负新值，在新图上的u到v的最短路上的点和原图上最短路上的点相同且顺序不变。

思路：
参考了多篇题解，我们造一个超级源点与每一个点相连，且边权为0，从超级源点开始跑spfa;
我们这m条边的新值为d[u]-d[v]+cost(u,v);
证明：
spfa松弛的条件是d[u]+cost(u,v)<d[v],所以d[u]+cost(u,v)-d[v]>=0;
如果新图有一条路为u-x1-x2-v。
则路的距离为d[u]+cost(u,x1)-d[x1]+d[x1]+cost(x1,x2)-d[x2]+d[x2]+cost(x2,v)-d[v]。
化简为：d[u]-d[v]+cost(u,x1)+cost(x1,x2)+cost(x2,v)。
又因为对于d[u]和d[v]是固定的，所以与原图最短路相同且顺序不变。

代码：

#include <bits/stdc++.h>

#define inf 1000000007
#define eps 0.00000001
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int maxn=100005;

inline int read()
{
    char c=getchar();
    int f=1, x=0;
    while(c>'9'||c<'0')
    {
        if(c=='-')
        {
            f=-1;
        }
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return f*x;
}

struct w
{
    int to, cost;
}w;

struct edge
{
    int u, v, w;
}edge[10005];

vector<struct w> g[10005];

int d[10005], use[10005];

void spfa()
{
   int p=0;
   fill(d,d+10005,inf);
   queue<int> q;
   q.push(p);
   d[0]=0;
   //printf("asd");
   while(!q.empty())
   {
       p=q.front();
       q.pop();
       int v=p;
       use[v]=0;
       for(int i=0;i<g[v].size();i++)
       {
           if(d[v]+g[v][i].cost<d[g[v][i].to])
           {
               d[g[v][i].to]=d[v]+g[v][i].cost;
               if(use[g[v][i].to]==0)
               {
                   p=g[v][i].to;
                   use[g[v][i].to]=1;
                   q.push(p);
               }
           }
       }
   }
}

int main()
{
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int u, v, t;
        scanf("%d%d%d",&u,&v,&t);
        edge[i].u=u;
        edge[i].v=v;
        edge[i].w=t;
        w.to=v;
        w.cost=t;
        g[u].push_back(w);
    }
    w.cost=0;
    for(int i=1;i<=n;i++)
    {
        w.to=i;
        g[0].push_back(w);
    }
    spfa();
    for(int i=0;i<m;i++)
    {
        printf("%d %d %d\n",edge[i].u,edge[i].v,d[edge[i].u]-d[edge[i].v]+edge[i].w);
    }
    return 0;
}