#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;

vector<tip> v[50001];

int d[50001];

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

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