#include <bits/stdc++.h>
#define MAX 50005

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int dist[MAX];
vector<pair<int,int>>vec[MAX];
bitset<MAX>B;
int cnt[MAX];

int main()
{
    int n,m;
    fin>>n>>m;
    while(m--)
    {
        int x,y,z;
        fin>>x>>y>>z;
        vec[x].push_back({y,z});
    }
    queue<int>q;
    int i;
    for(i=2;i<=n;++i)
        dist[i]=1e9;
    q.push(1);
    B[1]=1;
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        B[nod]=0;
        for(i=0;i<vec[nod].size();++i)
            if(dist[nod]+vec[nod][i].second<dist[vec[nod][i].first])
            {
                dist[vec[nod][i].first]=dist[nod]+vec[nod][i].second;
                if(!B[vec[nod][i].first]){
                q.push(vec[nod][i].first);
                ++cnt[vec[nod][i].first];
                B[vec[nod][i].first]=1;
                if(cnt[vec[nod][i].first]>n)
                {
                    fout<<"Ciclu negativ!";
                    return 0;
                }
                }
            }
    }
    for(i=2;i<=n;++i)
        fout<<dist[i]<<' ';
    return 0;
}