#include <bits/stdc++.h>
#define pb push_back

using namespace std;

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

void debug_out() { cerr << '\n'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}
#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

typedef pair<int,int> pii;
typedef long long int ll;
typedef long double ld;

const int DMAX = 5e4+10;

struct nume{
    int node,val;
};

vector <nume> arb[DMAX];
priority_queue <nume> heap;

int dp[DMAX];
bool uz[DMAX];

int n,m;

inline bool operator<(nume x,nume y){
    return x.val>y.val;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t,i,j;
    int x,y,z;

    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>z;
        arb[x].pb({y,z});
    }
    for(i=2;i<=n;i++)
        dp[i]=2e9;
    heap.push({1,0});
    while(!heap.empty()){
        nume node=heap.top();
        heap.pop();
        uz[node.node]=false;
        for(auto& it:arb[node.node])
            if(dp[it.node] > dp[node.node]+it.val){
                dp[it.node]=dp[node.node]+it.val;
                if(!uz[it.node]){
                    uz[it.node]=true;
                    heap.push({it.node,dp[it.node]});
                }
            }
    }
    for(i=2;i<=n;i++)
        (dp[i] != 2e9)?fout<<dp[i]<<' ':fout<<"0 ";
    fout<<'\n';

    return 0;
}