#include <cstdio>

using namespace std;

const int MAX_N = 50000, MAX_M = 250000, MAX_L = 1000, INF = MAX_L*MAX_N+1;

int lst[MAX_N+1], urm[MAX_M+1], vf[MAX_M+1], c[MAX_M+1];
int nrg;

int d[MAX_N+1];

FILE *in, *out;

int n, m;

void add(int x, int y, int z)
{
    nrg++;
    urm[nrg] = lst[x];
    vf[nrg] = y;
    c[nrg] = z;
    lst[x] = nrg;
}

int h[MAX_N+1];
int nh;

void change(int p1, int p2)
{
    int aux = h[p1];
    h[p1] = h[p2];
    h[p2] = aux;
}

void urca(int p)
{
    while(p != 1 && d[h[p]] < d[h[p/2]])
    {
        change(p, p/2);
        p /= 2;
    }
}

void coboara(int p)
{
    int fs = 2*p, fd = fs+1, bun = p;
    if(fs <= nh && d[h[bun]] > d[h[fs]])
        bun = fs;
    if(fd <= nh && d[h[bun]] > d[h[fd]])
        bun = fd;
    if(bun != p)
    {
        change(bun, p);
        coboara(bun);
    }
}

void push(int x)
{
    h[++nh] = x;
    urca(nh);
}

int pop()
{
    change(1, nh--);
    coboara(1);
    return h[nh+1];
}

bool viz[MAX_N+1];

void init()
{
    for(int i = 2; i <= n; i++)
        d[i] = INF;
    d[1] = 0;
    push(1);
}

void relax(int u, int v, int w)
{
    if(d[v] > d[u]+w)
    {
        d[v] = d[u]+w;
        push(v);
    }
}

void dijkstra()
{
    init();
    int u, p;
    while(nh > 0)
    {
        u = pop();
        p = lst[u];
        while(p != 0)
        {
            relax(u,vf[p], c[p]);
            p = urm[p];
        }
    }
}

int main()
{
    in = fopen("dijkstra.in", "r");
    out = fopen("dijkstra.out", "w");
    fscanf(in, "%d%d", &n, &m);
    int x, y, z;
    for(int i = 0; i < m; i++)
    {
        fscanf(in, "%d%d%d", &x, &y, &z);
        add(x,y,z);
    }
    dijkstra();
    for(int i = 2; i <= n; i++)
        fprintf(out, "%d ", d[i]);
    fcloseall();
    return 0;
}