#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#define INF 1e9
using namespace std;
const int NMAX = 50001;

vector <pair<int,int> > G[NMAX];
pair<int, int> H[NMAX];
int nod_poz[NMAX];
int size_heap;
int distante[NMAX];

int father(int nod){
    return nod/2;
}
int left_son(int nod){
    return 2*nod;
}
int right_son(int nod){
    return 2*nod + 1;
}
void swap(int poz1, int poz2){
    pair <int, int> aux;
    aux = H[poz1];
    H[poz1] = H[poz2];
    H[poz2] = aux;
}
void up_heap(int nod){
    while(nod > 1 && H[nod].first < H[father(nod)].first){
        nod_poz[H[nod].second] = father(nod);
        nod_poz[H[father(nod)].second] = nod;
        swap(nod, father(nod));
        nod = father(nod);
    }
}
void down_heap(int nod){
    int son;
    do{
        son = 0;
        if(right_son(nod) <= size_heap && H[nod].first > H[right_son(nod)].first)
            son = right_son(nod);
        if(left_son(nod) <= size_heap && H[nod].first > H[left_son(nod)].first && H[left_son(nod)] < H[right_son(nod)])
            son = left_son(nod);
        if(son){
            nod_poz[H[nod].second] = son;
            nod_poz[H[son].second] = nod;
            swap(nod, son);
        }
        nod = son;
    }while(son);
}
void update_heap(int poz, int new_value){
    H[poz].first = new_value;
    if(H[poz].first < H[father(poz)].first)
        up_heap(poz);
    else
        down_heap(poz);
}
void erase_top_heap(){
    nod_poz[H[1].second] = -1;
    swap(1,size_heap);
    size_heap --;
    down_heap(1);
}
void insert_heap(int value, int nod){
    H[++size_heap] = make_pair(value,nod);
    nod_poz[nod] = size_heap;
    up_heap(size_heap);
}
pair<int, int> top(){
    return H[1];
}

int main()
{
    FILE *fin, *fout;
    int n,m,i,nod1,nod2,w,nod,p;
    fin = fopen("dijkstra.in","r");
    fout = fopen("dijkstra.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(fin,"%d %d %d",&nod1,&nod2,&w);
        G[nod1].push_back(make_pair(nod2,w));
    }
    distante[1] = 0;
    for(i=2;i<=n;i++)
        distante[i] = INF, nod_poz[i] = -1;
    insert_heap(distante[1], 1);
    while(size_heap){
        nod = top().second;
        erase_top_heap();
        for(p=0;p<G[nod].size();p++)
            if(distante[G[nod][p].first] > distante[nod] + G[nod][p].second){
                distante[G[nod][p].first] = distante[nod] + G[nod][p].second;
                if(nod_poz[G[nod][p].first] == -1)
                    insert_heap(distante[G[nod][p].first], G[nod][p].first);
                else
                    update_heap(nod_poz[G[nod][p].first], distante[G[nod][p].first]);
            }
    }
    for(i=2;i<=n;i++)
        if(distante[i] != INF)
            fprintf(fout,"%d ",distante[i]);
        else
            fprintf(fout,"0 ");
    fclose(fin);
    fclose(fout);
    return 0;
}