///complexity: O(m*ln(n))
#include <bits/stdc++.h>
#define NMAX 50005
#define INF 2e9
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n, m, x, y, pas, sem;
int path[NMAX], visited[NMAX];
vector < pair< int, int > > nod[NMAX];
queue <  int  > q;

void read(){
    f>>n>>m;
    for(int i = 1; i <= m; ++i){
        f>>x>>y>>pas;
        nod[x].push_back(make_pair(y, pas));
    }
    path[1] = 0;
    q.push(1);
    f.close();
}

void dijkstra(int node){
    int next_node;
    for(int i = 2; i <= n; ++i)
        path[i] = INF;
    while(!q.empty()){
        next_node = q.front();
        visited[next_node]++;
        q.pop();
        if(visited[next_node] > n){
            g<<"Ciclu negativ!";
            sem = 1;
            break;
        }
        for(auto it:nod[next_node])
            if(path[it.first] > path[next_node] + it.second){
                path[it.first] = path[next_node] + it.second;
                q.push(it.first);
            }
    }
}

int main()
{
    read();
    dijkstra(1);
    if(sem)
        return 0;
    for(int i = 2; i <= n; ++i)
        g<<path[i]<<' ';
    g.close();
    return 0;
}