#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

const int inf=1<<30;
const int max_n=50001;

//ifstream f("bellmanford.in");
//ofstream g("bellmanford.out");

struct muchie
{
    int x;
    int c;
};

vector <muchie> a[max_n];
int n,m,viz[max_n],cost[max_n],coada[250001];

void bf()
{
    freopen ("bellmanford.out","w",stdout);
    int p,u,i,y,k;
    p=0;
    u=1;
    viz[1]=1;
    coada[u]=1;
    for(i=2;i<=n;i++)
       cost[i]=inf;

    while(p!=u)
    {
        p++;
        y=coada[p];
        for(i=0;i<a[y].size();i++)
        {
			k=a[y][i].x;
			if(cost[y]+a[y][i].c<cost[k])
			{
				cost[k]=cost[y]+a[y][i].c;
				if(viz[k]>n && cost[k]<0)
				{
				    printf("Ciclu negativ!");
					//g<<"Ciclu negativ!";
					return;
				}
				viz[y]++;
				u++;
				coada[u]=k;
			}
        }
    }
        for(i=2;i<=n;i++)
        {
		if(cost[i]==inf){
		printf("0\n");
		//	g<<"0\n";
         continue;}
			printf("%d ",cost[i]);
				//	g<<cost[i]<<" ";
    }

}

int main()
{
    freopen ("bellmanford.in","r",stdin);
    muchie aux;
    scanf("%d%d",&n,&m);
   // f>>n>>m;
    for(int i=1;i<=m;i++)
     {
         int p,q,k;
         scanf("%d%d%d",&p,&q,&k);
         //f>>p>>q>>k;
         aux.x=q;
         aux.c=k;
         a[p].push_back(aux);
     }
    bf();
    return 0;
}