#include <bits/stdc++.h>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int nMax = 50003;
const int inf = 1e9;
struct Elem{
    int nod, cost;
    inline bool operator < (const Elem &A) const {
        return cost > A.cost;
    }
};
vector <Elem> Graf[nMax];
priority_queue <Elem> Q;
int dp[nMax];
inline void Dij() {
    Elem coada;
    coada.nod = 1;
    coada.cost = 1;
    Q.push(coada);
    while(!Q.empty()) {
        int nodulet = Q.top().nod;
        int costulet = Q.top().cost;
        Q.pop();
        for(const auto &i : Graf[nodulet]) {
            int newnod = i.nod;
            int newcost = i.cost;
            if(dp[newnod] > dp[nodulet] + newcost) {
                dp[newnod] = dp[nodulet] + newcost;
                Elem nval;
                nval.nod = newnod;
                nval.cost = dp[newnod];
                Q.push(nval);
            }
        }
    }
}
int main()
{
    int n, m, x, y, c;
    f >> n >> m;
    Elem val;
    for(int i = 1; i <= m; i++) {
        f >> x >> y >> c;
        val.nod = y;
        val.cost = c;
        Graf[x].push_back(val);
    }
    for(int i = 1; i <= n; i++) {
        dp[i] = inf;
    }
    dp[1] = 0;
    Dij();
    for(int i = 2; i <= n; i++) {
        if(dp[i] != inf) {
            g << dp[i] << " ";
        }
    }
    return 0;
}