#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], heap[MAXM], vpoz[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=2; i<=n; i++) d[i] = INF;
    nh=n;
    for(i=1; i<=n; i++) heap[i]=vpoz[i]=i;
    while(1)
    {
        if(nh==0)
            break;
        bnod = heap[1];
        del(1);
        if(d[bnod]==INF) break;
        for(i=0; i<v[bnod].size(); i++)
        {
            w=v[bnod][i].second;
            b=v[bnod][i].first;
            if(d[bnod] + w < d[b]){
                d[b] = d[bnod] + w;
                upheap(vpoz[b]);
            }
        }

    }
    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[poz]],vpoz[heap[tata]]);
        upheap(tata);
    }
}
void del(int poz)
{
    swap(heap[1],heap[nh]);
    swap(vpoz[heap[1]],vpoz[heap[nh]]);
    nh--;
    downheap(1);
}
void downheap(int poz)
{
    int fiu;
    if(poz*2 > nh) return;
    fiu = poz*2+(poz*2+1<nh and d[poz*2]>d[poz*2+1]);
    if(d[heap[poz]] > d[heap[fiu]])
    {
        swap(heap[poz],heap[fiu]);
        swap(vpoz[heap[poz]],vpoz[heap[fiu]]);
        downheap(fiu);
    }
}