#include<fstream>
#include<algorithm>
#define INF 0x3f3f
using namespace std;

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

int D[50001], T[50001];
char U[50001];
int n, m, k;

struct lista
{
    int nod, cost;
    lista *urm;
} *G[50001];

void adauga(int i, int j, int k)
{
    lista *p;
    p = new lista;
    p->nod = j;
    p->cost = k;
    p->urm = G[i];
    G[i] = p;
}

void citire()
{
    f >> n >> m;
    int x, y, z;
    while(m--)
    {
        f >> x >> y >> z;
        adauga(x, y, z);
    }
}

void dijkstra(int s)
{
    int nod,mini;
    for(int i=1; i<=n; i++)
            D[i] = INF;

    D[s]=0;

    while(1)
    {
        mini = INF;

        for(int i=1; i<=n; i++)
            if( !U[i] && mini>D[i] )
                mini = D[i], nod = i;
        if(mini==INF) break;

        U[nod]=1;
        lista *p = G[nod];

        for(; p; p=p->urm)
            if( D[p->nod] > D[nod] + p->cost && !U[p->nod] )
                D[p->nod] = D[nod] + p->cost, T[p->nod] = nod;
    }
}
int main()
{
    citire();
    dijkstra(1);

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