#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#define MAX 1000000000
#define N 50100


using namespace std;

class cmp{
public:

    bool operator() (pair<int, int> d1, pair<int, int> d2){
        return d1.second > d2.second;
    }
};

int dist[N];
int viz[N];
int n,m;

vector < pair<int , int> > muc[N];
vector < pair<int , int> >::iterator it;


priority_queue < pair<int,int>, vector< pair <int,int> >, cmp  > que;

void dijkstra(int st){
    static int i,nod;

    que.push( make_pair(st , 0 ) );

    for(i=1;i<=n;i++){
        dist[i]=MAX;
    }
    dist[st]=0;

    while( !que.empty()){
        while( !que.empty() && viz[ que.top().first ]  ){
            que.pop();
        }

        if(que.empty() ) {
            break;
        }

        nod=que.top().first;
        que.pop();

        viz[nod]=1;

        for(it=muc[nod].begin(); it!=muc[nod].end() ;it++ ){
            if( viz[it->first]==0 ){
                if( dist[it->first]>dist[nod]+ it->second  ){
                    dist[it->first]=dist[nod]+ it->second;
                    que.push( make_pair(it->first,dist[it->first] ) );
                }

            }
        }
    }
}


int main(){
    int x,y,z,i;

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    scanf("%d%d", &n, &m);

    for(i=0 ; i<m ; i++){
        scanf("%d %d %d", &x, &y, &z);
        muc[x].push_back( make_pair(y,z) );
    }

    dijkstra(1);

    for(i=2;i<=n;i++){
        if(dist[i]==MAX){
            printf("0 ");
            continue;
        }
        printf("%d ",dist[i]);
    }

    return 0;
}