#include <bits/stdc++.h>

using namespace std;

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

vector<pair<int, int>> graf[50003];   //perechi sa tinem distanta
priority_queue<pair<int, int>> q;
int minim[50003];

void dijkstra(int src) {

    q.push ( make_pair ( 0 , src ) ) ;
	minim [src] = 0 ;

    while (!q.empty()) {
        int nod = q.top().second;
        q.pop();

        for (auto& v : graf[nod]) {

            if (minim[nod] + v.second < minim[v.first]) {
                //am gasit un drum mai scurt deci actualizam
                minim[v.first] = minim[nod] + v.second;
                q.push(make_pair(minim[v.first], v.first )); //punem perechea in coada pentru a o utiliza ulterior
            }
        }
    }
}


int main()
{
    int n, m;

    fin>>n>>m;

    for (int i = 1; i <= n; i++)
        minim[i] = INT_MAX;

    for (int i = 1; i <= m; i++) {
        int x, y, z;
        fin >> x >> y >> z;
        graf[x].push_back({y, z});  //distanta de la x la y este z
//        graf[y].push_back({x, z});  //distanta de la y la x este z
    }
    dijkstra(1);
    for(int i=2; i<=n; i++){
        fout<<minim[i]<<' ';
    }
}