#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#define nmax 50001
#define inf 10e9

using namespace std;

set < pair <int,int> > s;
vector <pair <int,int> > v[nmax];
int dist[nmax];

void dij(int start){
    int i;
    for(i=0;i<v[start].size();i++){
        s.insert({v[start][i].first,v[start][i].second});
    }
    while(!s.empty()){
        int x=s.begin()->first;
        int y=s.begin()->second;
        s.erase(s.begin());
        if(dist[y]>x){
            dist[y]=x;
            for(i=0;i<v[y].size();i++){
                s.insert({x+v[y][i].first,v[y][i].second});
            }
        }
    }
}

void initial(int n){
    for(int i=0;i<=n;i++){
        dist[i]=inf;
    }
}

int main()
{
    FILE *fin, *fout;
    int n,m,i,j,c;
    fin=fopen("dijkstra.in","r");
    fout=fopen("dijkstra.out","w");
    fscanf(fin,"%d%d",&n,&m);
    for(m;m>0;m--){
        fscanf(fin,"%d%d%d",&i,&j,&c);
        v[i].push_back({c,j});
    }
    initial(n);
    dij(1);
    for(i=2;i<=n;i++){
        if(dist[i]==inf)
            fprintf(fout,"0 ");
        else
            fprintf(fout,"%d ",dist[i]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}