#include <bits/stdc++.h>
#define optim ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ll long long
#define ull unsigned long long
#define popcount(x) __builtin_popcount(x)
#define ctzll(x) __builtin_ctzll(x)
#define clzll(x) __builtin_clzll(x)

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");


const int sze = 5e5;

vector<pair<int, int>> G[sze + 1];
int D[sze + 1];
int n;
class compare{
    public:
    bool operator()(int a,int b){
        return D[a] > D[b];
    }
};
bitset<sze + 1> F;
void Dijkstra(int st){
    for(int i = 1;i<=n;++i) D[i] = INT_MAX;
    priority_queue<int, vector<int>, compare> q;
    q.push(st);
    D[st] = 0;
    while(!q.empty()){
        auto t = q.top();
        q.pop();
        if(F[t]) continue;
        F[t] = 1;
        for(auto i : G[t]){
            if(D[t] + i.second < D[i.first]){
                D[i.first] = D[t] + i.second;
                q.push(i.first);
            }
        }
    }
}


int main()
{
    int m;
    fin>>n>>m;
    int a, b, c;
    for(int i = 1;i<=m;++i){
        fin>>a>>b>>c;
        G[a].push_back({b, c});
    }
    Dijkstra(1);
    for(int i = 2;i<=n;++i) fout<<D[i]<<' ';




    return 0;
}