#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

const int NMAX=50005;
const int INF=(1<<30);

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

int n,m;
int x,y,c;

vector<pair<int,int>> Muchii[NMAX];
int distanta[NMAX];
bool vizitat[NMAX];

struct compare{
    bool operator()(int x,int y){
        return distanta[x]>distanta[y];
    }
};

void dijkstra(int start){
    priority_queue<int, vector<int>, compare> Q;
    Q.push(start);
    vizitat[start]=true;
    distanta[start]=0;
    while(!Q.empty()){
        int nod=Q.top();
        Q.pop();
        vizitat[nod]=false;
        for(unsigned int i=0;i<Muchii[nod].size();i++){
            int vecin=Muchii[nod][i].first;
            int cost=Muchii[nod][i].second;
            if(distanta[nod]+cost<distanta[vecin]){
                distanta[vecin]=distanta[nod]+cost;
                if(!vizitat[vecin]){
                    vizitat[vecin]=true;
                    Q.push(vecin);
                }
            }
        }
    }
}

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