#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <climits>
#include <stack>

using namespace std;

vector <pair <int, int> > v[100001];
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m, a, b, vd[50000], vv[50000], vt[50000], cost;

void init()
{
    for(int i = 1; i<=100000; i++)
        vd[i] = INT_MAX;
}

int bfs()
{
    int p, cs;
    while(!pq.empty())
    {
        p = pq.top().second;
        cs = pq.top().first;
        pq.pop();

        vv[p]++;
        if(vv[p] > n)
        {
            cout<<"Ciclu negativ!";
            return -1;
        }


        for(auto x : v[p])
        {
            if(cs+x.second < vd[x.first])
            {
                vd[x.first] = cs+x.second;
                vt[x.first] = p;
                pq.push({vd[x.first], x.first});
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    for(int i = 1; i<=m; i++)
    {
        fin>>a>>b>>cost;
        v[a].push_back({b, cost});
    }
    pq.push({0, 1});
    init();
    if(bfs() != -1)
        for(int i = 2; i<=n; i++)
            fout<<vd[i]<<' ';
}