#include <fstream>
#include <vector>
#include <queue>

#define NMAX 50005
#define INF 10000000005

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

queue<int> q;

int n, m, x0;
int x, y, c;
vector<pair<int, int>> l[NMAX];
int dmin[NMAX], pre[NMAX];
int nr[NMAX];
int i, j;

int bellmanford();

int main()
{
    ///CITIRE
    fin >>n>>m; x0 = 1;

    for (i = 1; i <= m; ++i)
    {
        fin >>x>>y>>c;
        l[x].push_back({y, c});
    }

    ///AFISARE
    if (!bellmanford()) fout <<"Ciclu negativ!";
    else
        for (i = 2; i <= n; ++i)
            fout <<dmin[i]<<' ';

    fout <<'\n';
    fout.close();
    return 0;
}

int bellmanford()
{
    int i;
    bool negativ = 0;
    for (i = 1; i <= n; ++i)
        dmin[i] = INF, pre[i] = x0;
    dmin[x0] = pre[x0] = 0;

    q.push(x0); int vf, vfnou, costnou;
    while (!negativ && !q.empty())
    {
        vf= q.front(); q.pop();
        for (i = 0; i < l[vf].size(); ++i)
        {
            vfnou = l[vf][i].first;
            costnou = l[vf][i].second;
            if (dmin[vfnou] > dmin[vf] + costnou)
            {
                dmin[vfnou] = dmin[vf] + costnou;
                nr[vfnou] ++;
                q.push(vfnou);
                if (nr[vfnou] > n) negativ = 1;
            }
        }
    }

    return 1;
}