#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
ifstream fin("dijkstra.in"); ofstream fout("dijkstra.out");

int n, m;
vector<pair<int, int> > heap;
vector<vector<pair<int, int>> > g;
bool v[50010];
int d[50010];


int bs(int l, int r, int x){
int tm=(l+r)/2;

if(l==r){return tm;}

if(heap[tm].ft>=x){return bs( l, tm, x);}
if(heap[tm].ft<x){return bs(tm+1, r, x);}

}




void dijkstra(){
int s=1;
d[1]=0;
heap.pb(mp(0, s) );

    while(!heap.empty()){
        int f=heap[0].sc;
        heap.erase(heap.begin(), heap.begin()+1 );
        if(v[f]==true){continue;}
        else{v[f]=true;}

        for(int i=0 ;i<g[f].size(); i++){

            if(!v[g[f][i].ft ] ){
                if(d[f]+g[f][i].sc<d[g[f][i].ft ]){
                    d[g[f][i].ft ]=d[f]+g[f][i].sc;
                    int c=bs(0, heap.size(), d[g[f][i].ft ]);
                            vector<pair<int, int>> tp; tp.pb(mp(d[g[f][i].ft ], g[f][i].ft ) );
                        heap.insert(heap.begin()+c, tp.begin(), tp.end());
                }
            }


        }

    }


}





int main(){
fin>>n>>m;
for(int i=1; i<=n; i++){d[i]=1000*1000*1000+1;}
g.resize(n+10);
for(int i=0; i<m;i++){
    int x, y, l;
    fin>>x>>y>>l;
    g[x].pb(mp(y, l) );
}

dijkstra();


for(int i=2; i<=n; i++){
    fout<<d[i]<<" ";
}



return 0;
}