#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m,a,b,c,dmin[50005],x,y,fr[50005];
struct eee
{
    int nod,cost;

};
vector<eee> v[50005];
queue<eee> q;
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>a>>b>>c;
        v[a].pb({b,c});
    }
    memset(dmin,inf,sizeof dmin);
    dmin[1]=0;
    q.push({1,0});
    int ok=1;
    while(!q.empty())
    {
        x=q.front().nod;
        y=q.front().cost;
        q.pop();
        if(fr[x]+1<=n && ok)
        {
            fr[x]++;
            for(auto i:v[x])
            {
                if(dmin[i.nod]>dmin[x]+i.cost)
                {
                    dmin[i.nod]=dmin[x]+i.cost;
                    q.push({i.nod,dmin[i.nod]});
                }
            }
        }
        else ok=0;
    }
    if(!ok)
    {
        out<<"Ciclu negativ!";
    }
    else for(int i=2;i<=n;i++)
    {
        out<<dmin[i]<<' ';
    }
    return 0;
}