#include <bits/stdc++.h>

using namespace std;

int PONDERI[1000][1000];
vector <int> PARINTE(100000);
vector <int> DISTANTA(100000);

void addEdge(vector <int> adj[], int u, int v){
    adj[u].push_back(v);
}

int main(){
    ifstream fin("dijkstra.in");
    int noduri, muchii;

    fin >> noduri >> muchii;

    for(int i = 1; i <= noduri; i++)
        for(int j = 1; j <= noduri; j++)
            PONDERI[i][j] = 0;

    vector <int> adj[noduri + 1];
    for(int i = 1; i <= muchii; i++){
        unsigned x, y, cost;
        fin >> x >> y >> cost;
        addEdge(adj, x, y);
        PONDERI[x][y] = cost;
        PONDERI[y][x] = cost;
    }

    for(int i = 1; i <= noduri; i++){
        DISTANTA[i] = 10000;
        PARINTE[i] = 0;
    }

    queue <int> coada;
    int start, finish;

    start = 1;
    DISTANTA[start] = 0;

    int nod;
    coada.push(start);
    while(!coada.empty()){
        nod = coada.front();
        coada.pop();

        for(auto it: adj[nod]){
            if(DISTANTA[nod] + PONDERI[nod][it] < DISTANTA[it]){
                DISTANTA[it] = DISTANTA[nod] + PONDERI[nod][it];
                PARINTE[it]  = nod;
                coada.push(it);
            }
        }
    }

    ofstream fout("dijkstra.out");
    for(int i = 2; i <= noduri; i++){
        fout << DISTANTA[i] << " ";
        cout << DISTANTA[i] << " ";
    }

    // for(auto it: PARINTE)
    //     cout << it << " ";

    // int sum = 0;
    // while(finish != start){
    //     cout << finish << " ";

    //     sum += PONDERI[finish][PARINTE[finish]];
    //     finish = PARINTE[finish];
    // }
    // cout << start << " Suma este: " << sum << endl;



    return 0;
}