#include <bits/stdc++.h>

using namespace std;

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

struct Nod{
    int a,cost;
};
vector <vector<Nod>> v;
int dist[250001];
int fr[50001],fr1[50001];
deque <int> q;

int main()
{
    int n,m;
    fin >> n >> m;
    v.resize(n+1);
    for (int i=1;i<=m;++i){
        int a,b,c;
        fin >> a >> b >> c;
        v[a].push_back({b,c});
    }
    for (int i=1;i<=n;++i) dist[i] = 1e9;
    dist[1] = 0;
    q.push_back(1);
    int lnod,nod,cnt = 0;
    while (!q.empty()){
        nod = q.front();
        fr1[nod]++;
        if (fr1[nod]>n){
            fout << "Ciclu negativ!";
            return 0;
        }
        q.pop_front();
        fr[nod] = 0;
        for (int i=0;i<v[nod].size();++i){
            if (dist[nod]+v[nod][i].cost<dist[v[nod][i].a]){
                if (!fr[v[nod][i].a]){
                    q.push_back(v[nod][i].a);
                    fr[nod] = 1;
                }
                dist[v[nod][i].a] = dist[nod]+v[nod][i].cost;
            }
        }
        lnod = n;
    }
    for (int i=2;i<=n;++i) fout << dist[i] << ' ';
    return 0;
}