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