#include <fstream>
#define INF 2000000
#define NMAX 1001
#define INFILE "dijkstra.in"
#define OUTFILE "dijkstra.out"
using namespace std;

struct Arc { int vf; int c; };

int n,x0;
Arc G[NMAX][NMAX];
int dmin[NMAX];
int prec[NMAX];
int M[NMAX];
int h[NMAX],lgh;
int poz[NMAX];

void citire();
void dijkstra();
int ExtracMin();
void Upgrade(int fiu);
void afisare();
void InsertHeap(int vf)
{
    h[++lgh] = vf;
    poz[vf] = lgh;
    Upgrade(lgh);
}

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}

void citire()
{
    ifstream fin(INFILE);
    int m,i,x,y,c;
    fin >> n >> m;
    x0 = 1;
    for(i = 0; i < m; i++)
    {
        fin >> x >> y >> c;
        G[x][0].c++;
        G[x][G[x][0].c].vf = y;
        G[x][G[x][0].c].c = c;
    }
    fin.close();
}
void dijkstra()
{
    int i,nrs = 1,j,vfmin;
    for(i = 1; i <= n; i++)
    {
        dmin[i] = INF;
        prec[i] = x0;
        poz[i] = -1;
    }
    dmin[x0] = 0;
    prec[x0] = -1;
    poz[x0] = 1;
    h[1] = x0;
    lgh = 1;

    while(nrs<n)
    {
        vfmin = ExtracMin();
        M[vfmin] = 1;
        nrs++;
        for(j = 1; j <= G[vfmin][0].c; j++)
        {
            if(!M[G[vfmin][j].vf]) //nu a fost deja selectat
            {
                if(dmin[G[vfmin][j].vf] > dmin[vfmin] + G[vfmin][j].c)
                {
                    dmin[G[vfmin][j].vf] = dmin[vfmin]+G[vfmin][j].c;
                    prec[G[vfmin][j].vf] = vfmin;
                    if(poz[G[vfmin][j].vf] == -1)
                        InsertHeap(G[vfmin][j].vf);
                    else Upgrade(poz[G[vfmin][j].vf]); //il promovez
                }
            }
        }
    }
}
int ExtracMin()
{
    int tata,fiu,tmp;
    int minim = h[1];
    h[1] = h[lgh--];
    poz[h[1]]=-1;
    tata = 1;
    fiu = 2*tata;
    while(fiu <= lgh)
    {
        if(fiu < lgh && dmin[h[fiu]] > dmin[h[fiu+1]]) fiu++;
        if(dmin[h[tata]] > dmin[h[fiu]])
        {
            poz[h[fiu]] = tata;
            poz[h[tata]] = fiu;
            tmp = h[fiu];
            h[fiu] = h[tata];
            h[tata] = tmp;
            tata = fiu;
            fiu = 2*tata;
        }
    }
    return minim;
}
void Upgrade(int fiu)
{
    int tata = fiu/2,tmp;
    while(tata && dmin[tata] > dmin[fiu])
    {
        poz[h[fiu]] = tata;
        poz[h[tata]] = fiu;
        tmp = h[fiu];
        h[fiu] = h[tata];
        h[tata] = tmp;
        fiu = tata;
        tata = fiu/2;
    }
}

void afisare()
{
    ofstream fout(OUTFILE);
    int i;
    for(i = 2; i <= n; i++)
    {
        fout << dmin[i] << ' ';
    }
    fout.close();
}