#include <iostream>
#include<stdio.h>
#include<vector>
#include<set>
#define nmax 50005
#define inf -1
using namespace std;
struct element{int n, c;};
int n, m, a, dmin[nmax], x, dist;
vector <element> ma[nmax];
vector <element> ::iterator it;
element el;
struct el_s{
    int dist, nod;
    bool operator<(const el_s& e) const{
        return dist<e.dist;
    }
    bool operator==(const el_s& e) const{
        return (dist==e.dist)&&(nod==e.nod);
    }
};
set <el_s> h;
el_s pr;
 
void citire(){
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++){
        scanf("%d %d %d",&a,&el.n,&el.c);
        ma[a].push_back(el);
    }
}
 
void rezolvare(){
    for (int i=2;i<=n;i++)
        dmin[i]=inf;
    dmin[1]=0;
    h.insert(el_s{.dist=0,.nod=1});
    while (h.size()){
        pr=*h.begin();
        h.erase(h.begin());
        x=pr.nod;    dist=pr.dist;
        for (it=ma[x].begin();it!=ma[x].end();it++)
            if ((dmin[(*it).n]>dist+(*it).c)||(dmin[(*it).n]==inf)){
                h.erase(el_s{.dist=dmin[(*it).n],.nod=(*it).n});
                dmin[(*it).n]=dist+(*it).c;
                h.insert(el_s{.dist=dmin[(*it).n],.nod=(*it).n});
            }
    }
    for (int i=2;i<=n;i++)
        if (dmin[i]==inf)
            printf("0 ");
        else
            printf("%d ",dmin[i]);
    printf("\n");
}
 
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    rezolvare();
    return 0;
}