#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

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

priority_queue<tip> q;

tip v[250001];

int muchii[250001][3],grad[50001];

tip* vecini[50001];

int d[50001];

void dijkstra(){
    while ( !q.empty() ){
        tip x=q.top();
        q.pop();
        for ( int i=0;i<grad[x.x];++i ){
            if ( d[vecini[x.x][i].x]>=d[x.x]+vecini[x.x][i].d ){
                d[vecini[x.x][i].x]=d[x.x]+vecini[x.x][i].d;
                q.push({vecini[x.x][i].x,d[vecini[x.x][i].x]});
            }
        }
    }
}

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<=m;++i ){
        fscanf(f,"%d%d%d",&a,&b,&c);
        muchii[i][0]=a;
        muchii[i][1]=b;
        muchii[i][2]=c;
        ++grad[muchii[i][0]];
    }
    vecini[1]=&v[0];
    for ( int i=2;i<=n;++i ){
        d[i]=2000000000;
        vecini[i]=vecini[i-1]+grad[i-1];
        grad[i-1]=0;
    }
    grad[n]=0;
    for ( int i=1;i<=m;++i ){
        vecini[muchii[i][0]][grad[muchii[i][0]]].x=muchii[i][1];
        vecini[muchii[i][0]][grad[muchii[i][0]]++].d=muchii[i][2];
    }
    d[1]=0;
    q.push({1,0});
    dijkstra();
    for ( int i=2;i<=n;++i ){
        if ( d[i]==2000000000 )d[i]=0;
        fprintf(h,"%d ",d[i]);
    }
    return 0;
}