#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct str{
    int nod, cost;
    bool operator < (const str&aux) const{
        return cost > aux.cost;
    }
};

const int maxint=2e9+2, maxsize=5e4+20;
int main()
{
    int d[maxsize], n, m;
    vector<pair<int, int>> mc[maxsize];
    priority_queue <str> pq;

    //citire
    fin>>n>>m;
    for(int i=1; i<=m; i++){
        int x, y, c;
        fin>>x>>y>>c;
        mc[x].push_back({y, c});
    }
    d[1]=0;
    for(int i=2; i<=n; i++) d[i]=maxint;

    //Dijkstra
    pq.push({1, 0});
    while(!pq.empty()){
        int cost=pq.top().cost, nod=pq.top().nod;
        pq.pop();
        if(cost>d[nod]) continue;
        for(size_t i=0; i<mc[nod].size(); i++){
            int vecin=mc[nod][i].first, costvecin=mc[nod][i].second;
            if(d[nod]+costvecin<d[vecin]){
                d[vecin]=d[nod]+costvecin;
                pq.push({vecin, d[vecin]});
            }
        }
    }
    for(int i=2; i<=n; i++) fout<<d[i]<<" ";

    return 0;
}