/*
		Keep It Simple!
*/

#include<cstdio>
#include<list>
#include<queue>

#define MaxN 50001
#define inf 1<<30

using namespace std;

int N,M,Dist[MaxN],cnt_InQ[MaxN];
bool InQ[MaxN],negative_cycle;
list< pair<int,int> > G[MaxN];
list<int> Queue;

void BellMan(int node)
{
		for(int i=2;i<=N;i++) Dist[i] = inf;
		Queue.push_back(1);
		InQ[1] = 1;
		while(Queue.size() && !negative_cycle)
		{
				int nod = Queue.front();
				Queue.pop_front();
				for(list< pair<int,int> >::iterator it = G[nod].begin(); it!=G[nod].end(); it++)
				{
						int r = it->first;
						Dist[it->first] = min(Dist[it->first],Dist[nod] + it->second);
   					if(!InQ[it->first] && (Dist[nod] + it->second) == Dist[it->first])
							{
									Queue.push_back(it->first);
									InQ[it->first] = 1;
									cnt_InQ[it->first]++;
							}
					if(cnt_InQ[it->first] > N)
						negative_cycle = true;
				}
				InQ[nod] = 0;
		}
}

int main()
{
		freopen("dijkstra.in","r",stdin);
		freopen("dijkstra.out","w",stdout);

		scanf("%d%d",&N,&M);
		int x,y,c;
		for(int i=1;i<=M;i++)
		{
				scanf("%d%d%d",&x,&y,&c);
				G[x].push_back( make_pair(y,c) );
    }

		BellMan(1);
		
		if(!negative_cycle)
		for(int i=2;i<=N;i++)
		{
			if(Dist[i] == inf)
				printf("0 ");
			else
				printf("%d ",Dist[i]);
		}
				else
			printf("Ciclu negativ!");
		return 0;
}