#include <cstdio>
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

#define MAXN 50050
#define INF 0x3f3f3f3f

FILE* fin = fopen ("dijkstra.in", "rb");
FILE* fout = fopen ("dijkstra.out", "w");

const int bufSize = 8192;
char buf[bufSize];
int ptr = bufSize - 1;

inline int getInt ()
{
    while (buf[ptr] < '0' || '9' < buf[ptr])
    {
        if (++ptr >= bufSize)
        {
            fread (buf, bufSize, 1, fin), ptr = 0;
        }
    }
    int nr = 0;
    while ('0' <= buf[ptr] && buf[ptr] <= '9')
    {
        nr = nr * 10 + buf[ptr] - '0';
        if (++ptr >= bufSize)
        {
            fread (buf, bufSize, 1, fin), ptr = 0;
        }
    }
    return nr;
}

typedef vector<pair<int,int> >::iterator iter;
int n, m, heap[MAXN], poz[MAXN], d[MAXN], l;
vector<pair<int,int> > g[MAXN];
bitset<MAXN> viz;

void swapH(int a,int b)
{
    int aux = heap[a];
    heap[a] = heap[b];
    heap[b] = aux;

    poz[heap[a]] = a;
    poz[heap[b]] = b;
}

void upHeap(int k)
{
    while((k >> 1) && d[heap[k >> 1]]>d[heap[k]])
    {
        swapH(k,k >> 1);
        k >>= 1;
    }
}

void downHeap(int p)
{
    int q = 0;
    while(q!=p)
    {
        q = p;
        if((q<<1) <= l && d[heap[q << 1]] < d[heap[p]]) p = q << 1;
        if((q<<1)+1 <= l && d[heap[(q << 1)+1]] < d[heap[p]]) p = (q << 1)+1;

        swapH(p,q);
    }
}

void dijkstra()
{
    for(int i = 1; i <= n; i++)
    {
        d[i] = INF;
        heap[i] = poz[i] = i;
    }

    d[1] = 0, l = n;

    while (l){
        int top = heap[1];
        viz[heap[1]] = true;
        swapH(1,l);
        l--;
        downHeap(1);

        for(iter it=g[top].begin(); it!=g[top].end(); it++)
        {
            if(!viz[it->first]&&(d[it->first]>d[top]+it->second))
            {
                d[it->first]=d[top]+it->second;
                upHeap(poz[it->first]);
            }
        }
    }
}

int main()
{
    FILE* fin=fopen("dijkstra.in","r");
    FILE* fout=fopen("dijkstra.out","w");

    n = getInt(), m = getInt();

    for(int i = 0; i < m; i++)
    {
        int x = getInt(), y = getInt(), c = getInt();
        g[x].push_back(make_pair(y, c));
    }

    dijkstra();

    for(int i = 2; i <= n; i++)
    {
        fprintf(fout, "%d ",(d[i] == INF) ? 0 : d[i]);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}