#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#define int long long


const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 0x3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 100 + 11;
const int NMAX = 1e4 + 11;
const ll INF64 = 3e18 + 1;
const double lil = 0.0000000000001;

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

int n, m;

vector<int>dist;
vector<vector<pi>>v;
priority_queue<pi, vector<pi>, greater<pi>>unmarked;


void Dijkstra(){

    unmarked.push({0,1});
    dist[1] = 0;

    while(!unmarked.empty()){

        int cur = unmarked.top().ss;
        int curDist = unmarked.top().ff;

        unmarked.pop();

        if(curDist != dist[cur])continue;

        for(auto it : v[cur]){

            int x = it.ff;
            int weight = it.ss;

            if(dist[cur] + weight < dist[x]){
                dist[x] = dist[cur] + weight;
                unmarked.push({dist[x],x});
            }
        }
    }
}

int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();

    in >> n >> m;

    v.resize(n + 5);
    dist.resize(n + 1, INF64);


    for(int i = 1, x, y, w; i <= m; i++){
        in >> x >> y >> w;
        v[x].push_back({y,w});
    }

    Dijkstra();

    for(int i = 2; i <= n; i++){
        out << dist[i] << ' ';
    }




}