#include <bits/stdc++.h>
#define mp make_pair

using namespace std;

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

const int nmax = 50005;
const int inf = 100005;
int n, m, cost[nmax];
vector< pair< int, pair<int, int> > > E;

void bellman(int nod)
{
    sort(E.begin(), E.end());
    for(int i = 1; i <= n; i ++)
        cost[i] = inf;

    int ok = 1; cost[nod] = 0;
    for(int i = 1; i < n && ok; i ++)
    {
        ok = 0;
        for(int j = 0; j < m; j ++)
        {
            int x = E[j].first;
            int y = E[j].second.first;
            int c = E[j].second.second;

            if(cost[y] > cost[x] + c)
                cost[y] = cost[x] + c, ok = 1;
        }

        for(int j = 0; j < m; j ++)
        {
            int x = E[j].first;
            int y = E[j].second.first;
            int c = E[j].second.second;

            if(cost[y] > cost[x] + c)
            {
                g << "Ciclu negativ!";
                exit(0);
            }
        }
    }
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int x, y, c;
        f >> x >> y >> c;
        E.push_back(mp(x, mp(y, c)));
    }

    bellman(1);

    for(int i = 2; i <= n; i ++)
        g << cost[i] << " ";
    return 0;
}