#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct Edge {
    int x, y, c;
};


const int NMAX = 10005;
int tata[NMAX];
vector<pair<int,int>> L[NMAX];
priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
int d[NMAX];
const int inf = 1e9;
int cost_curent;

void djk(const int start_node){
    d[start_node] = 0;
    tata[start_node] = -1;
    pq.push({d[start_node], start_node});

    while(!pq.empty()){
        int cost_curent = pq.top().first;
        int nod_curent = pq.top().second;
        pq.pop();

        if (cost_curent > d[nod_curent]) continue;


        for(const auto pair: L[nod_curent]){
            int cost_spre_vecin = pair.second;
            int vecin = pair.first;

            if(d[vecin] > cost_curent + cost_spre_vecin){
                d[vecin]= cost_curent + cost_spre_vecin;
                tata[vecin] = nod_curent;
                pq.push({d[vecin],vecin});
            }
        }
    }
}

int main(){
    int N, M, nod_start, nod_dest;
    fin >> N >> M;
    for(int i=1; i<=N;i++) d[i]=inf;

    // cout << "Nod start, nod destinatie: ";
    // cin >> nod_start >> nod_dest;

    for (int i=1; i<=M;i++) {
        Edge e;
        cin >> e.x >> e.y >> e.c;
        L[e.x].push_back({e.y, e.c});
    }
    djk(1);

    for (int i=2;i<=N;i++) {
        fout << d[i] <<  " ";
    }

    // cout << d[nod_dest]<< endl;
    //
    // int nod = nod_dest;
    // while (tata[nod]!=-1) {
    //     cout << nod << "->";
    //     nod = tata[nod];
    // }
    // cout << nod_start;
}