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

using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
#define MaxN 50002
#define Max 1e9
struct st
{
    int nod, cost;
};
vector<st> graph[MaxN];
queue<int> coada;
int dist[MaxN];
int marked[MaxN];
int cnt[MaxN];
int n, ok=0;
void add(int a, int b, int cost)
{
    graph[a].push_back({b, cost});
}

void bellman(int nod)
{
    int i, q;
    for(i=1; i<=n; i++)
    {
        dist[i]=Max;
    }
    dist[nod]=0;
    cnt[nod]++;
    coada.push(nod);
    marked[nod]=1;

    while(!coada.empty() && cnt[q=coada.front()]<n)
    {
        for(const st& i: graph[q])
        {
            if(dist[i.nod]>dist[q]+i.cost)
            {
                dist[i.nod]=dist[q]+i.cost;
                cnt[i.nod]++;
                if(marked[i.nod]==0)
                {
                    coada.push(i.nod);
                    marked[i.nod]=1;
                }
            }
        }
        marked[q]=0;
        coada.pop();
    }
   if(!coada.empty())
    { out<<"Ciclu negativ!"; ok=1;}
}
int main()
{
    int m, i, j, cost, a, b;
    in>>n>>m;
    for(i=0; i<m; i++)
    {
        in>>a>>b>>cost;
        add(a, b, cost);
    }
    bellman(1);
    if(ok==0)
    {
        for(i=2; i<=n; i++)
        {
            out<<dist[i]<<" ";
        }
    }
    return 0;
}