#include <fstream>
#include <set>
#include <vector>
#include <cstring>
#define DIM 50005
#define INF 20000000

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int N, M;

int dist[DIM];

vector < pair <int, int> > Edge[DIM];
struct cmp{
    int operator()(const pair <int, int> &x, const pair<int, int>& y){

        if(x.second < y.second)
            return 1;
        return 0;

    }
};

set < pair <int, int> , cmp> Heap;

int main(){

    fin >> N >> M;

    while(M --){
        int x, y, d;

        fin >> x >> y >> d;

        Edge[x].push_back(make_pair(y, d));
    }

    memset(dist, 0xF, DIM * sizeof(int));

    dist[1] = 0;

    Heap.insert(make_pair(1, 0));

    while(!Heap.empty()){

        int node = Heap.begin() -> first;
        Heap.erase(Heap.begin());
        //vector < pair <int, int> >::iterator it = Edge[node -> first].begin();

        for(vector < pair <int, int> >::iterator it = Edge[node].begin(); it != Edge[node].end(); it ++){

            if(dist[it -> first] > dist[node] + it -> second){
                dist[it -> first] = dist[node] + it -> second;
                Heap.insert(make_pair(it -> first, dist[it -> first]));
            }

        }

    }

    for(int i = 2; i <= N; i ++)
        fout << dist[i] << " ";

    fout << "\n";

    return 0;

}