#include<bits/stdc++.h>

#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define nod first
#define cost second

using namespace std;

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

//--declaration
const int NMAX = 50000;
vector< pair<int, int> > G[NMAX];
queue<int> q;
int n, m, x, y, c;
//--end declaration

int main()
{
    int D[NMAX], ItNod[NMAX];
    bool USED[NMAX];
    f>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        f>>x>>y>>c;
        G[x].pb( mp(y, c) );
    }


    memset(D, inf, sizeof(D));
    memset(USED, false, sizeof(USED));

    int START = 1;
    D[START] = 0;
    q.push(START);
    USED[START] = true;
    ItNod[START] = 1;

    while(!q.empty())
    {
        int Nod = q.front();
        q.pop();
        USED[Nod] = false;
        for(int i = 0; i < G[Nod].size(); i++)
        {
            if( D[(G[Nod][i]).nod] > D[Nod] + (G[Nod][i]).cost)
            {
                D[(G[Nod][i]).nod] = D[Nod] + (G[Nod][i]).cost;
                if(!USED[(G[Nod][i]).nod])
                {
                    USED[(G[Nod][i]).nod] = true;
                    q.push((G[Nod][i]).nod);
                    ItNod[(G[Nod][i]).nod] ++;
                    if(ItNod[(G[Nod][i]).nod] > n)
                    {
                        g<<"Ciclu negativ!"<<"\n";
                        return 0;
                    }
                }
            }
        }
    }

    for(int i = 2; i <= n; i++) g<<D[i]<<" ";

    return 0;
}