#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int NMAX = 50003;
const int INF = 1e9;
int dp[NMAX];
struct cmp{
    inline bool operator ()(const int A,const int B)
    {
        return dp[A] > dp[B];
    }
};
priority_queue <int, vector <int>, cmp> Q;
vector < pair < int ,int > > G[NMAX];
bool viz[NMAX];
inline void Dijkstra() {
    Q.push(1);
    while(!Q.empty()) {
        int nod = Q.top();
        Q.pop();
        if(viz[nod] == 1)
            continue;
        viz[nod] = 1; 
        for(auto i: G[nod]) {
            int y = i.first;
            int cost = dp[nod] + i.second;
            if(dp[y] > cost) {
                dp[y] = cost;
                Q.push(y);
            }
        }
    }
}
int main() {
    int n, m;
    f>> n >> m;
    while (m--) {
        int x, y , c;
        f>> x >> y >> c;
        G[x].push_back(make_pair(y,c));
    }
    for(int i = 2;i <= n; ++i)
        dp[i] = INF;
    Dijkstra();
    for(int i = 2;i <= n; ++i)
        g<<( dp[i] != INF? dp[i] : 0 )<<" ";
    g<<"\n";
    return 0;
}