/*****************************************
备注：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define int long long
const int N = 1e6 + 10;
const int INF = 2147483647;
int n,m,s;
int head[N],to[N],w[N],id,ne[N];
void add(int x,int y,int z)
{
	to[++id]=y ,ne[id]=head[x],w[id]=z,head[x]=id;
}
struct node
{
	int id,num;
	bool operator<(const node &a)const 
	{
		return num>a.num;
	}
};
long long dis[N],vis[N];
void dijkstra()
{
	for(int i=0;i<=n;i++)
		dis[i]=INF;
	dis[s]=0;
	priority_queue<node>p;
	p.push((node){s,0});
	while(!p.empty())
	{
		node t=p.top();
		p.pop();
		if(t.num!=dis[t.id]||vis[t.id]) 
			continue;
		vis[t.id] = 1;
		for(int i=head[t.id];i;i = ne[i])
		{
			if(!vis[to[i]]&&dis[to[i]]>t.num+w[i])
			{
				dis[to[i]]=t.num+w[i];
				p.push((node){to[i],dis[to[i]]});
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(dis[i]==INF)
		{
			cout<<"-1"<<" ";
		}
		else
		{
			cout<<dis[i]<< " ";
		}
	}
		
}
signed main()
{
	cin>>n>>m;
	s=1;
	for(int i=0;i<m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	dijkstra();
	return 0;
}

题目没说有负环呀，为什么WA