#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int n,m,s,cnt,head[N],dis[N];
bool vis[N];
struct qedge{
	int to,nextt,quan;
}edge[N * 2];
void addedge(int x,int y,int z){
	edge[++cnt].to = y;
	edge[cnt].quan = z;
	edge[cnt].nextt = head[x];
	head[x] = cnt;
}
queue<int> q;
int main(){
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		addedge(a,b,c);
	}
	for(int i = 1;i <= n;i++) dis[i] = 2147483647;
	q.push(1);
	vis[1] = 1;
	dis[1] = 0;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = 1;
		for(int i = head[u];i;i = edge[i].nextt){
			int v = edge[i].to;
			if(dis[v] > dis[u] + edge[i].quan){
				dis[v] = dis[u] + edge[i].quan;
				if(!vis[v]){
					q.push(v);
					vis[v] = 1;
				}
			}
		}
	}
	for(int i = 1;i <= n;i++){
		if(dis[i] == 2147483647) cout<<-1<<" ";
		else cout<<dis[i]<<" ";
	}
}

为了AC这道题，我专门学了不想学的spfa（以前都敲dijkatra）