#include <iostream>
#include <fstream>
#include <queue>
#include <cstdlib>

using namespace std;
const int maxn = 5e4+5, inf = 0x3f3f3f3f;

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

typedef struct nod {
    int i, c;
    nod *next;
} *pNod;
pNod v[maxn];

void add(int x, int y, int z) {
    pNod p = new nod;
    p -> i = y;
    p -> c = z;
    p -> next = v[x];
    v[x] = p;
}

int ans[maxn];
int done[maxn];

class pqc
{
public:
    bool operator () (int x, int y) {
        return (ans[x] > ans[y]);
    }
};

priority_queue <int, vector<int>, pqc> q;

int n, m;

void dij()
{
    int i, j, x;
    for(i = 2; i <= n; i ++) {
        ans[i] = inf;
    }
    q.push(1);

    while(!q.empty())
    {
        x = q.top();
        q.pop();
        done[x] = false;
        for(pNod p = v[x]; p != NULL; p = p -> next)
        {
            if(ans[x] + (p -> c) < ans[p -> i])
            {
                ans[p -> i] = ans[x] + (p -> c);
                if(done[p -> i] == false)
                {
                    q.push(p -> i);
                    done[p -> i] = true;
                }
            }
        }
    }
}

// bellman ford
queue <int> bq;
void bf()
{
    int i, j;
    bool ok = false;

    for(i = 2; i <= n; i ++) {
        ans[i] = inf;
    }

    for(i = 1; i <= n-1; i ++)
    {
        ok = false;
        bq.push(1);
        //done[1] ++;
        while(!bq.empty())
        {
            j = bq.front();
            bq.pop();
            for(pNod p = v[j]; p != NULL; p = p -> next)
            {
                if(ans[j] + (p -> c) < ans[p -> i]/* && done[p -> i] < i*/)
                {
                    ok = true;
                    ans[p -> i] = ans[j] + (p -> c);
                    //done[p -> i] ++;
                    bq.push(p -> i);
                }
            }
        }

        if(ok == false)
        {
            return;
        }
    }
    g << "Ciclu negativ!";
    exit(0);
}

int main()
{
    int i, x, y, z;
    f >> n >> m;

    for(i = 1; i <= m; i ++) {
        f >> x >> y >> z;
        add(x, y, z);
    }

    bf();
    //dij();

    for(i = 2; i <= n; i ++) {
        if(ans[i] == inf)
            g << "0 ";
        else
            g << ans[i] << ' ';
    }

    f.close();
    g.close();
    return 0;
}