#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define inf 1000000000
#define maxN 50002
using namespace std;
int n, m, i, j, s, vis[maxN], d[maxN];
vector < pair < int, int > > V[maxN];
queue < int > q;
void read()
{
    int x, y, z;
    freopen("bellmanford.in", "r", stdin);
    scanf("%d %d", &n, &m);
    s = 1;
    for (i = 1; i <= m; ++ i)
    {
        scanf("%d %d %d", &x, &y, &z);
        V[x].push_back(make_pair(y, z));
    }
}
void solve()
{
    int x, node;
    for (i = 1; i <= n; ++ i)
        d[i] = inf;
    d[s] = 0;
    q.push(s);
    while (!q.empty())
    {
        x = q.front();
        q.pop();
        ++ vis[x];
        if (vis[x] > n)
        {
            freopen("bellmanford.out", "w", stdout);
            printf("Ciclu negativ!");
            exit(0);
        }
        for (i = 0; i < V[x].size(); ++ i)
        {
            node = V[x][i].first;
            if (d[node] > d[x] + V[x][i].second)
            {
                d[node] = d[x] + V[x][i].second;
                q.push(node);
            }
        }
    }
}
void write()
{
    freopen("bellmanford.out", "w", stdout);
    for (i = 2; i <= n; ++ i)
        printf("%d ", d[i]);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}