#include <iostream>
#include <fstream>
#define MAXn 50000
#define MAXm 250000
#define inf 1000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct nod
{
    int y,z;
    nod *urm;
};
nod *lis[MAXn],*p;
int n,m,i,j,x,y,z,dist[MAXn],viz[MAXn],minw,k;
bool doing = true;

void citire()
{
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        p = new nod;
        f >> x >> y >> z;
        p->y = y;
        p->z = z;
        p->urm = lis[x];
        lis[x] = p;
    }
}

void dijkstra(int sursa)
{
    for(i=1; i<=n; i++)
        dist[i] = inf;
    for(p = lis[sursa]; p!=NULL; p=p->urm)
        dist[p->y] = p->z;
    dist[sursa] = 0; viz[sursa] = 1;
    while(doing)
    {
        minw = inf;
        for(i=1; i<=n; i++)
            if(!viz[i] && dist[i] < minw)
                minw = dist[i], k=i;

        if(minw != inf)
        {
            viz[k] = 1;
            for(p = lis[k]; p != NULL; p = p->urm)
                if(!viz[p->y] && dist[p->y] > dist[k] + p->z)
                    dist[p->y] = dist[k] + p->z;
        }
        else
            doing = false;
    }

}

int main()
{
    citire();
    dijkstra(1);
    for(i=2; i<=n; i++)
        g << dist[i] << ' ';
    return 0;
}