#include <fstream>
#include <set>
#include <vector>
#define INF 1000000002
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int i, j, n, m, x, y, c;
int d[50002];
vector <pair<int, int>> L[50002];
void dijkstra(){
    for(int i=1;i<=n;i++){
        d[i]=INF;
    }
    d[1]=0;
    set <pair<int, int>> s;
    s.insert({0, 1});
    while(!s.empty()){
        int nod=s.begin()->second;
        s.erase(s.begin());
        for(int i=0;i<L[nod].size();i++){
            int vecin=L[nod][i].first;
            int cost=L[nod][i].second;
            if(d[vecin]>d[nod]+cost){
                s.erase({d[vecin], vecin});
                d[vecin]=d[nod]+cost;
                s.insert({d[vecin], vecin});
            }
        }

    }



}
int main() {
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>x>>y>>c;
        L[x].push_back({y, c});
    }
    dijkstra();
    for(i=2;i<=n;i++){
        if(d[i]!=INF)
        cout<<d[i]<<" ";
        else
            cout<<0<<" ";
    }



}