#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#define maxn 50001
#define inf 999999999
int n, m, cn=0;
vector <pair<int, int> > g[50001];
vector <int> dst(maxn, inf);
void citire()
{
    fin>>n>>m;
    int i, j, c;
    for(int k=1; k<=m; k++)
    {
        fin>>i>>j>>c;
        g[i].push_back(make_pair(j, c));
    }
    fin.close();
}
void BellmanFord()
{
    vector <int> cnt_in_q(maxn, 0);
    queue <int> q;
    bool inCoada[maxn]={0};
    int k;
    vector <pair<int, int> > :: iterator it;
    dst[1]=0; q.push(1); inCoada[1]=1;
    while(!cn && !q.empty())
    {
        k=q.front();
        q.pop();
        inCoada[k]=0;
        for(it=g[k].begin(); it!=g[k].end(); it++)
            if(dst[k]<inf)
                if(dst[it->first]>dst[k]+it->second)
                {
                    dst[it->first]=dst[k]+it->second;
                    if(!inCoada[it->first])
                    {
                        if(cnt_in_q[it->first]>n)
                            cn=1;
                        else
                        {
                            q.push(it->first);
                            inCoada[it->first]=1;
                            cnt_in_q[it->first]++;
                        }
                    }
                }
    }
}
int main()
{
    citire();
    BellmanFord();
    if(cn)
        fout<<"Ciclu negativ!";
    else for(int i=2; i<=n; i++)
        fout<<dst[i]<<" ";
    return 0;
}