#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <cassert>
#include <vector>
#include <set>
#include <cstring>
using namespace std;

#define nmax 100050
#define INF 0x3f3f3f3f
void read();
void dijkstra();

int n,m;
vector<pair<int,int> >G[nmax];
int dist[nmax];


int main()
{
    read();
    dijkstra();


    FILE * fout = fopen("dijkstra.out","w");

    for(int i=2;i<=n;i++){
        if(dist[i] == INF)
            dist[i] = 0;
        fprintf(fout,"%d ", dist[i]);
    }

    return 0;
}

void read(){

    FILE * fin = fopen("dijkstra.in","r");

    fscanf(fin,"%d %d", &n, &m);


    for(int i=1;i<=m;i++){
        int x,y,c;
        fscanf(fin,"%d %d %d", &x, &y, &c);
        G[x].push_back(make_pair(y,c));
    }

}

void dijkstra(){

    memset(dist, INF, sizeof dist);
    dist[1] = 0;
    set<pair<int,int> > Set;
    Set.insert(make_pair(0,1));

    while(!Set.empty()){
        int node = Set.begin()->second;
        int distance = Set.begin()->first;
        Set.erase(Set.begin());

        for(vector<pair<int,int> >::iterator it = G[node].begin(); it != G[node].end(); ++it){
            int y = it->first;
            int c = it->second;

            if(dist[y] > dist[node] + c){
                if(dist[y] != INF){
                    Set.erase(Set.find(make_pair(dist[y],y)));
                }

                dist[y] = dist[node] + c;
                Set.insert(make_pair(dist[y],y));
            }
        }


    }
}