#include <bits/stdc++.h>


using namespace std;
///bellmanford
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

queue <int> q;
vector <pair<int,int>> graf[50001];

int n,m, viz[50001];
long long d[50001];

void citire() {
    int x,y,c;
    fin >> n >> m;
    for (int i=1;i<=m;i++) {
        fin >> x >> y >> c;
        graf[x].push_back({y,c});
        //graf[y].push_back({x,c});
    }
    for (int i=1;i<=n;i++){
        d[i]=INT_MAX;
    }
}

int alg(){
    int nod;
    q.push(1);
    nod=1;
    d[1]=0;
    while (!q.empty())
    {
        q.pop();
        viz[nod]++;
        if (viz[nod]>n) {
            fout << "Ciclu negativ!";
            return 0;///Oprim executarea
        }
        for (pair<int,int> el: graf[nod])
        {
            if (d[el.first]>d[nod]+el.second)
            {
                d[el.first]=d[nod]+el.second;
                q.push(el.first);
            }
        }
        nod=q.front();
    }
    return 1;
}

int main()
{
    citire();
    if (alg()) for (int i=2;i<=n;i++) {
        fout << d[i] << " ";
    }
}