#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>

#define INF (1<<30)
#define mod 666013

using namespace std;
typedef pair<int, int> pereche;
int n, m, i, x, y, z, c[50005], inq[50005];
pereche mch;
vector <pereche> v[50005];
vector <pereche>::iterator it;
queue <int> q;
int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d%d", &n, &m);
    while(m--)
    {
        scanf("%d%d%d", &x, &y, &z);
        mch.first = y;
        mch.second = z;
        v[x].push_back(mch);
    }
    c[1] = 0;
    for(i = 2; i <= n; i++)
        c[i] = INF;
    q.push(1);
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        inq[x] = 0;
        for(it = v[x].begin(); it != v[x].end(); it++)
        {
            mch = *it;
            y = mch.first;
            z = mch.second;
            if(c[x] + z < c[y])
            {
                c[y] = c[x] + z;
                inq[y] = 1;
                q.push(y);
            }
        }
        if(c[1] < 0)
        {
            printf("Ciclu negativ!");
            return 0;
        }
    }
    for(i = 2; i <= n; i++)
        printf("%d ", c[i]);
    return 0;
}