#include <iostream>
#include <fstream>
#define maxi 999999999
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,a,c1,b,t[3][500001],k,start[500001],cost[50001],c[50001],viz[50001],cnt[50001],ok=1;
void ford(int p)
{
    int i,ps=1,pi=1,val,k;
    for(i=1;i<=n;i++)
        cost[i]=maxi;
    cost[p]=0;
    c[pi]=p;
    while(ps<=pi)
    {
        k=c[ps];
        viz[k]=0;
        val=start[k];
        while(val)
        {
            if(cost[k]+t[2][val]<cost[t[0][val]])
            {

                  cost[t[0][val]]=cost[k]+t[2][val];
                  cnt[t[0][val]]++;
                  if(cnt[t[0][val]]>n)
                  {
                        ok=0;
                        break;
                  }

                  if(!viz[t[0][val]])
                    viz[t[0][val]]=1, c[++pi]=t[0][val];
            }
                val=t[1][val];
        }
        ps++;
        if(ok==0)
            break;

    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c1;
        k++;
        t[0][k]=b;
        t[1][k]=start[a];
        t[2][k]=c1;
        start[a]=k;
    }
    ford(1);
    if(ok==0)
        g<<"Ciclu negativ!";
    for(int i=2;i<=n;i++)
    {
       g<<cost[i]<<" ";
    }

        return 0;
}