#include <fstream>
#include<vector>
using namespace std;
vector<pair<int,int> > v[50001];
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,s,i,j,viz[50001],q[50001],nr[50001],dist[50001],x,y,z,k,ok=1;
void bellmanford(int k){
    int p=1,u=1;
    q[p]=k;
    viz[k]=1;
    nr[k]=1;
    dist[k]=0;
    while(p<=u){
        k=q[p];
        for(i=0;i<v[k].size();i++)
            {
                int d=v[k][i].first;
                int c=v[k][i].second;
                if(dist[d]>dist[k]+c)
                {
                    dist[d]=dist[k]+c;
                    nr[d]++;
                    if(nr[d]>n-1)
                        {   ok=0;
                            g<<"Ciclu negativ!";
                            return;
                        }
                    if(viz[d]==0)
                    {
                        u++;
                        q[u]=d;
                        viz[d]=1;
                    }
                }
            }
      p++;
      viz[k]=0;

    }

}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
     {
        f>>x>>y>>z;
        v[x].push_back(make_pair(y,z));

     }
     for(i=1;i<=n;i++)
        dist[i]=250000001;
    bellmanford(1);
    if(ok==1)
    for(i=2;i<=n;i++)
        g<<dist[i]<<" ";

    return 0;
}