#include<bits/stdc++.h>
#define st first
#define nd second
#define maxn 50005
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;

vector<pair<int,int> >::iterator it;
vector<pair<int,int> > v[maxn];
int dist[maxn],heap[maxn],poz[maxn],n,m,k;

void read(){
    int x,y,c;
    cin>>n>>m;
    while(m--){
        cin>>x>>y>>c;
        v[x].pb({y,c});
    }
}

void upheap(int nod){
    while(nod!=1&& dist[heap[nod]]<dist[heap[nod/2]]){
        swap(heap[nod],heap[nod/2]);
        swap(poz[heap[nod]],poz[heap[nod/2]]);
        nod/=2;
    }
}

void downheap(int nod){
    int son=1;
    while(son){
        son=0;
        if(2*nod<=k && dist[heap[nod]]>dist[heap[nod*2]])
            son=2*nod;
        if(2*nod+1<=k && dist[heap[nod]]>dist[heap[2*nod+1]] && dist[heap[2*nod]]>dist[heap[2*nod+1]])
            son=2*nod+1;
        swap(heap[nod],heap[son]);
        swap(poz[heap[nod]],poz[heap[son]]);
        nod=son;
    }
}


void solve(){
    memset(dist,inf,sizeof(dist));
    dist[1]=0;
    heap[++k]=poz[1]=1;
    while(k){
        int nod=heap[1];
        poz[nod]=0;
        swap(heap[1],heap[k]);
        poz[heap[1]]=1;
        k--; downheap(1);
        for(it=v[nod].begin(); it!=v[nod].end(); it++){
             if(dist[(*it).st]>dist[nod]+(*it).nd){
                dist[(*it).st]=dist[nod]+(*it).nd;
                 if(poz[(*it).st]==0)
                    poz[(*it).st]=++k, heap[k]=(*it).st, upheap(k);
                 else upheap(poz[(*it).st]);
             }
        }
    }
    for(int i=2; i<=n; i++)
        if(dist[i]==inf)
            cout<<0<<' ';
        else
            cout<<dist[i]<<' ';

}

int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    read();
    solve();
}