#include <bits/stdc++.h>

using namespace std;

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 ( { 0 , src }) ;
	minim [src] = 0 ;

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

        for (auto& vecin : graf[nod]) {
            int next_nod = vecin.first, cost_next_nod = vecin.second;
            if (minim[nod] + cost_next_nod < minim[next_nod]) {
                //am gasit un drum mai scurt deci actualizam
                minim[next_nod] = minim[nod] + cost_next_nod;
                q.push({-minim[next_nod], next_nod}); //punem perechea in coada pentru a o utiliza ulterior
            }
        }
    }
}


int main()
{
    int n, m;

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

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

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

    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &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++){
        if(minim[i] == 1e9)
            printf("0 ");
        else
            printf("%d", minim[i]);
    }
}