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

using namespace std;

const int maxn=50001;
const int inf=1073741824;
int n,nr, m, s, cost[maxn],viz[maxn],coada[500002];
struct muchie{
  int x;
  int c;
}x;


vector<muchie> a[maxn];
int u;
bool ciclu=0;

void bellmanf()
{
  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!");
					return;
				}
				viz[y]++;
				u++;
				coada[u]=k;
			}
        }
    }
        for(i=2;i<=n;i++)
        {
		if(cost[i]==inf){
		printf("0\n");
         continue;}
			printf("%d ",cost[i]);
    }

}


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