#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define inf 200001
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector <pair <int,int> >a[50001];
bool v[50001];
int dcof[50001];
queue <int>q;
int main()
{
    int d[50001];
    int nod,n,m,i,x,y,c;
    f >> n >> m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x].pb(mp(y,c));
    }
    memset(d,inf,sizeof(d));
    q.push(1);
    v[1] = true;
    //dcof[1] = 1;
    d[1] = 0;
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        v[x] = false;
        for(i=0;i < a[x].size() ; i++)
        {
            nod = a[x][i].first;
            c = a[x][i].second;
            if(d[nod] > d[x] + c)
            {
                d[nod] = d[x] + c;
                if(v[nod]==false)
                    {q.push(nod);v[nod]=true;}
                dcof[nod]++;
                if(dcof[nod]>n)
                {
                    g<<"Ciclu Negativ!";
                    return 0;
                }
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        g<<d[i]<<" ";
    }
}