#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];
int cnt[MAX];

class cmp
{
public:
    bool operator()(pair<int,int> a,pair<int,int> b)
    {
        return a.second<b.second;
    }
};

int main()
{
    int n,m;
    fin>>n>>m;
    while(m--)
    {
        int x,y,z;
        fin>>x>>y>>z;
        vec[x].push_back({y,z});
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>pq;
    int i;
    for(i=2;i<=n;++i)
        dist[i]=1e9;
    pq.push({1,0});
    while(!pq.empty())
    {
        int nod=pq.top().first;
        int val=pq.top().second;
        pq.pop();
        if(dist[nod]<val)
            continue;
        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;
                pq.push({vec[nod][i].first,dist[vec[nod][i].first]});
                ++cnt[vec[nod][i].first];
                if(cnt[vec[nod][i].first]>n)
                {
                    fout<<"Ciclu negativ!";
                    return 0;
                }
            }
    }
    for(i=2;i<=n;++i)
        fout<<dist[i]<<' ';
    return 0;
}