#include <iostream>
#include <fstream>
#define oo 199999999
using namespace std;

int a[20000][20000], coada[20000], distante[20000], vizitat[20000], qfront, qback;

ifstream f("bellmanford.in");
ofstream fout("bellmanford.out");
void bellman_ford(int start, int n)
{
    int i, nod;
    for(i=1; i<=n; i++)
        distante[i]=oo;
    distante[start]=0;
    vizitat[start]=1;

    qfront=1; qback=0;
    coada[++qback]=start; // diferenta dintre i++ si ++i o vezi aici http://stackoverflow.com/questions/24853/what-is-the-difference-between-i-and-i

    while(qfront<=qback)
    {
        nod=coada[qfront];
        qfront++;

        vizitat[nod]++;    // habar nu am ce fac liniile astea
        if(vizitat[nod]>n)
        {
            fout << "Ciclu negativ!";
            break;
        }
        for(i=1; i<=n; i++)
            if(a[nod][i]!=0)
                if(distante[i]>distante[nod]+a[nod][i])
                {
                    distante[i]=distante[nod]+a[nod][i];
                    coada[++qback]=i;
                }
    }
}
int main()
{
    int n, m, i=0, x, y, cost;
    f >> n >> m; // m numarul de muchii !!! am facut pe orientat
    while(i<m)
    {
        f >> x >> y >> cost;
        a[x][y]=cost;
        i++;
    }

    bellman_ford(1, n);
    for(i=2; i<=n; i++)
        fout << distante[i] << " ";

    return 0;
}