#include <cstdio>
#include <queue>

using namespace std;

struct tip{
    int x,d;
    const bool operator < ( const tip &other )const{
        return d>other.d;
    }
};

priority_queue<tip> q;

struct cop{
    int va,ur,co;
};
cop v[250001];

int d[50001],list[100001];

void dijkstra(){
    while ( !q.empty() ){
        tip x=q.top();q.pop();
        int poz=list[x.x];
        while ( poz!=-1 ){
            int y=v[poz].va;
            if ( d[y]>d[x.x]+v[poz].co ){
                d[y]=d[x.x]+v[poz].co;
                q.push({y,d[y]});
            }
            poz=v[poz].ur;
        }
    }
}

FILE*f=fopen("dijkstra.in","r");
FILE*h=fopen("dijkstra.out","w");

int main()
{
    int n,m,a,b,c;
    fscanf(f,"%d%d",&n,&m);
    for ( int i=1;i<=n;++i ){
        d[i]=2000000000;
        list[i]=-1;
    }
    int nr=0;
    for ( int i=1;i<=m;++i ){
        fscanf(f,"%d%d%d",&a,&b,&c);
        v[nr].va=b;
        v[nr].ur=list[a];
        v[nr].co=c;
        list[a]=nr++;
    }
    d[1]=0;
    q.push({1,0});
    dijkstra();
    for ( int i=1;i<=n;++i )
        if ( d[i]==2000000000 )d[i]=0;
    for ( int i=2;i<=n;++i )
        fprintf(h,"%d ",d[i]);
    return 0;
}