#include <fstream>
#include <stdint.h>
using namespace std;
fstream f1("dijkstra.in", ios::in);
fstream f2("dijkstra.out", ios::out);
///afla drumurile minime de la un nod dat(in cazul problemei nodul 1 la toate celelalte noduri
///folosesti un vecor dist= dist de la nodul 1 la nodul i
///initializat cu val a[1][i] matricea costurilor
///si un vector pred, pred[i]= predecesorul lui i in drumul minim de la i la 1
///initializat cu val 1, cu exceptia p[1]=0(nodul 1 nu este precedat de nimeni
///alegi n-1 varfuri, conditia este ca nodul selectat sa nu mai fi fost selectat(viz[i]=0)
///si ca dist[i] sa fie minim
///cand selectezi un nod reactualizezi dist de la celelalte noduri la 1, incercand un drum intermediar
///prin nodul selectat
int32_t n, m,  pred[50001], dist[50001], vfmin, mini, a[10001][10001], viz[50001];
const int32_t  inf=9999999;
int main()
{
    int32_t i, x, y, c, j;
    f1>>n>>m;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(i!=j) a[i][j]=inf;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y>>c;
        a[x][y]=c;///graf orientat
    }
    ///init dijkstra
    pred[1]=0;
    dist[1]=0;
    viz[1]=1;
    for(i=2; i<=n; i++)
    {
        dist[i]=a[1][i];
        pred[i]=1;
    }
    ///selectezi n-1 noduri
    for(i=1; i<=n-1; i++)
    {
        ///cauti vf minim din cele neselectate
        mini=inf;
        for(j=2; j<=n; j++)
            if((!viz[j])&&(mini>dist[j])) {mini=dist[j]; vfmin=j;}

        ///il vizitezi
        viz[vfmin]=1;
        ///si reactualizezi dist de la 1 la celelalte noduri nevizitate
        ///daca dist de la 1 la j> dist de la 1 la vfmin + dist de la vfmin la j
        for(j=2; j<=n; j++)
            if((!viz[j])&&(dist[j]>(a[vfmin][j]+dist[vfmin])))
        {
            dist[j]=a[vfmin][j]+dist[vfmin];
            pred[j]=vfmin;
            ///vfmin il precede pe j in drumul de la j la i, adica face legatura intre j si i
        }
    }
    ///afisarea dist
    for(i=2; i<=n; i++)
        if(dist[i]!=inf) f2<<dist[i]<<" ";
        else f2<<0<<" ";
    return 0;
}