#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX = 50000 + 5, INF = INT_MAX/2;

vector<pair<int,int> > v[N_MAX];
int n,m,cost[N_MAX];

priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > q;
bitset<N_MAX> inq;

void dijkstra(int cost[N_MAX]){

    for(int i = 1; i<=n; ++i)
        cost[i] = INF;

    cost[1] = 0;
    q.push({0,1});

    while(!q.empty()){
        int nod = q.top().second;
        inq[nod] = false;
        q.pop();

        for(auto i : v[nod]){
            if(cost[nod] + i.second < cost[i.first]){
                cost[i.first] = cost[nod] + i.second;
                if(!inq[i.first]){
                    q.push({cost[i.first], i.first});
                    inq[i.first] = true;
                }
            }
        }
    }

}

int main()
{
    fin >> n >> m;
    for (int i = 1,a,b,c; i<=m; ++i){
        fin >> a >> b >> c;
        v[a].push_back({b,c});
    }

    dijkstra(cost);

    for(int i = 2; i <= n; ++i){
        if(cost[i] == INF)
            cost[i] = 0;
        fout << cost[i] << " ";
    }

    return 0;
}