/// Bellman-Ford (cu coada)
#include <bits/stdc++.h>
#define Nmax 50006
#define INF 1000000000
using namespace std;
ifstream f("bellmanford.in"); ofstream g("bellmanford.out");
int D[Nmax],use[Nmax];
struct vecin {int varf,cost;};
vector <vecin> L[Nmax];
queue <int> Q;
int main()
{   int n,m;
    f>>n>>m;
    for(int x,y,c;m;--m) {f>>x>>y>>c; L[x].push_back((vecin){y,c});}
    for(int i=1;i<=n;i++) D[i]=INF;
    Q.push(1); D[1]=0;
    while(!Q.empty())
    {   int x=Q.front(); Q.pop();
        use[x]++;
        if(use[x]==n) {g<<"Ciclu negativ!\n"; g.close(); f.close(); return 0;}
        vector <vecin> :: iterator it=L[x].begin(), sf=L[x].end();
        for(;it!=sf;++it)
        {   if(D[(*it).varf]>D[x]+(*it).cost)
            {    D[(*it).varf]=D[x]+(*it).cost;
                Q.push((*it).varf);
            }
        }
    }
    for(int i=2;i<=n;i++) g<<D[i]<<" ";
    g<<'\n'; g.close(); f.close(); return 0;
}