#include <fstream>
#include <queue>
#include <stdlib.h>

using namespace std;

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

const int INF = 500000000;

int n, m;

struct Road
{
    int len, connect;
};

queue <int> pq;

int final[50005];

vector <Road> v[50005];

int visit[50005];

void Bellman()
{
    while(!pq.empty())
    {
        int in = pq.front();
        pq.pop();
        for(int i = 0; i < v[in].size(); i++)
        {
            int length = v[in][i].len + final[in];
            if(length < final[v[in][i].connect])
            {
                visit[v[in][i].connect]++;

                if(visit[v[in][i].connect] > n)
                {
                    fout << "Ciclu negativ\n";
                    exit(0);
                }

                final[v[in][i].connect] = length;
                pq.push(v[in][i].connect);
            }
        }
    }

}

int main(void)
{
    fin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int a;
        Road node;
        fin >> a >> node.connect >> node.len;
        v[a].push_back(node);
    }
    pq.push(1);
    visit[1] = 1;

    for(int i = 2; i <= n; i++)
        final[i] = INF;

    Bellman();

    for(int i = 2; i <= n; i++)
        fout << final[i] <<' ';
}