#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <cstring>

using namespace std;

struct node{
    int v, cost;
    node(int v, int cost){
        this->v = v;
        this->cost = cost;
    }
    bool operator<(const node& other) const {
        if(this->cost == other.cost)
            return this->v < other.v;
        return this->cost < other.cost;
    }
    bool operator>(const node& other) const {
        if(this->cost == other.cost)
            return this->v > other.v;
        return this->cost > other.cost;
    }
};

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

bool didIputitinset[50005];
vector<node> adjancy[50005];
int distances[50005], n, m;
set<node> S;

void solve(){
    S.insert(node(0, 0));
    didIputitinset[0] = true;
    distances[0] = 0;
    while(!S.empty()){
        node nod = *S.begin();
        didIputitinset[nod.v] = false;
        S.erase(S.begin());
        for (auto &i : adjancy[nod.v]) {
            if(nod.cost + i.cost < distances[i.v]){
                if(didIputitinset[i.v]){
                    S.erase(S.find(node(i.v, distances[i.v])));
                    didIputitinset[i.v] = false;
                }
                distances[i.v] = nod.cost + i.cost;
                S.insert(node(i.v, distances[i.v]));
                didIputitinset[i.v] = true;
            }
        }
    }
}

int main() {
    f>>n>>m;
    for (int i = 0; i < m; ++i) {
        int source, destination, cost;
        f>>source>>destination>>cost;
        adjancy[source - 1].emplace_back(destination - 1, cost);
    }
    memset(distances, 11, sizeof(distances));
    solve();
    for(int i = 1; i < n; ++i){
        g<<distances[i]<<' ';
    }
    return 0;
}