Description：

给一个带权有向图，更改边的权值使得所有边权非负且所有原来的两点间的最短路径（即经过的点的顺序）不变。

$1\leqslant n\leqslant 10^5$

Solution：

从 $0$ 号节点向所有点连边权为 $0$ 的边，求出最短路数组 $d[i]$ ，那么更改所有边 $(u,v,w)$ 为 $(u,v,d[u]-d[v]+w)$ 。

证明一下：由三角形不等式 $d[v]\leqslant d[u]+w$ 得 $d[u]-d[v]+w\geqslant 0$ ，原来的最短路设为 $(u,x_1,x_2,\dots,x_k,v)$ ，现在的距离为 $d[u]-d[x_1]+w_1+d[x_1]-d[x_2]+w_2+\cdots+d[x_k]-d[v]+w_k$ ，发现很多 $d$ 能消掉，最后变成了 $d[u]+原来最短路-d[v]$ ， $d[u]$ 和 $d[v]$ 都是确定的，所以合法。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1010

#define MAXM 3010

struct edges

{

	int u,v,w;

}es[MAXM];

struct edge

{

	int to,nxt,v;

}e[MAXM];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	return;

}

int d[MAXN];

bool inq[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].w);

		add(es[i].u,es[i].v,es[i].w);

	}

	for(int i = 1;i <= n;++i)add(0,i,0);

	queue<int> q;q.push(0);

	memset(d,0x3f,sizeof(d));d[0] = 0;

	memset(inq,false,sizeof(inq));inq[0] = true;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		inq[k] = false;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				if(!inq[e[i].to])

				{

					inq[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	for(int i = 1;i <= m;++i)

	{

		printf("%d %d %d\n",es[i].u,es[i].v,d[es[i].u] - d[es[i].v] + es[i].w);

	}

	return 0;

}