#include <iostream>
#include <stdio.h>
#include <set>
#include <vector>

using namespace std;

const int N = 50005;
const int INF = 1<<30;
const char inf[] = "dijkstra.in";
const char outf[] = "dijkstra.out";

int n,m,d[N];
set<pair<int,int> > h;
vector<pair<int,int> > a[N];
bool viz[N];

void dijkstra(){
    int i,j,k;
    for(i=1;i<=n;i++)
        d[i]=INF;
    h.insert(make_pair(0,1));

    while(!h.empty()){
        j=(*h.begin()).second;
        k=(*h.begin()).first;
        h.erase(h.begin());

        for(i=0;i<a[j].size();i++)
            if(d[a[j][i].first]>a[j][i].second+k){
                d[a[j][i].first]=a[j][i].second+k;
                h.insert(make_pair(d[a[j][i].first],a[j][i].first));
        }
    }
}

int main()
{
    freopen(inf,"r",stdin);
    freopen(outf,"w",stdout);
    int i,j,k,l;

    scanf("%d %d",&n,&m);
    for(l=1;l<=m;l++){
        scanf("%d %d %d",&i,&j,&k);
        a[i].push_back(make_pair(j,k));
    }
    dijkstra();

    for(i=2;i<=n;i++)
        if(d[i]!=INF)
            printf("%d ",d[i]);
        else
            printf("0 ");
    return 0;
}