#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
#define MAX 50005
#define MAXM 250005
#define INF 250000001

vector<pair <int, int> >v[MAX];

int d[MAX], vpoz[MAX], heap[MAX];
void del(int poz), upheap(int poz), downheap(int poz);
int n, m, nh;
int main()
{

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int i, a, b, w, bnod;
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d",&a,&b,&w);
        v[a].push_back(make_pair(b,w));

    }
    for(i=1; i<=n; i++)
    {
        d[i]=INF;
        heap[i] = vpoz[i] = i;
    }
    d[1]=0;
    nh=n;

    while(1)
    {
        if(nh==0)
            break;
        bnod = heap[1];

        if(d[bnod]==INF) break;

        for(i=0; i<(int)v[bnod].size(); i++)
        {
            a=bnod; w=v[bnod][i].second; b=v[bnod][i].first;
            if(d[a] + w < d[b]){
                d[v[bnod][i].first]=d[bnod] + v[bnod][i].second;
                upheap(vpoz[v[bnod][i].first]);
            }
        }
        del(1);

    }
    for(i=2; i<=n; i++)
    {
        if(d[i] == INF)
            printf("0 ");
        else
            printf("%d ",d[i]);
    }
    printf("\n");
    return 0;
}
void upheap(int poz)
{
    int tata;
    if(poz == 1) return;
    tata = poz/2;
    if(d[heap[tata]] > d[heap[poz]])
    {
        swap(heap[tata],heap[poz]);
        swap(vpoz[heap[tata]],vpoz[heap[poz]]);
        upheap(tata);
    }
}
void del(int poz)
{
    swap(heap[1],heap[nh]);
    swap(vpoz[heap[1]],vpoz[heap[poz]]);
    nh--;
    downheap(1);
}
void downheap(int poz)
{
    int fiu;
    if(poz*2 > nh) return;
    fiu = poz*2+(poz*2+1<=nh and d[heap[poz*2]]>d[heap[poz*2+1]]);
    if(d[heap[poz]] > d[heap[fiu]])
    {
        swap(heap[poz],heap[fiu]);
        swap(vpoz[heap[fiu]],vpoz[heap[poz]]);
        downheap(fiu);
    }
}