#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll


ifstream fin("dijkstra.in"); ofstream fout("dijkstra.out");
#define cin fin
#define cout fout



int n, m;
vector<pii> g[50001];
int d[50001]; bool v[50001];

void dijkstra(int d[]){

for(int i=2; i<=n; i++){
    d[i]=-1;
}
d[1]=0;
multiset<pii> ms;
ms.insert(mp(0, 1));

while(!ms.empty()){
    auto it=ms.begin();
    int du=it->ft, u=it->sc; v[u]=true;
    ms.erase(it);

    for(auto pr:g[u]){
        int u2=pr.ft, w=pr.sc;
        if(v[u2]){
            continue;
        }
        if(d[u2]==(-1)){
            d[u2]=du+w;
            ms.insert(mp(d[u2], u2));
        }
        else{
            if(d[u2]>(du+w)){
                ms.erase(mp(d[u2], u2) );
                d[u2]=du+w;
                ms.insert(mp(d[u2], u2) );
            }
        }
    }
}

}



int32_t main(){
INIT
cin>>n>>m;
for(int i=0; i<m; i++){
    int u, v, w;
    cin>>u>>v>>w;
    g[u].pb(mp(v, w));
}

dijkstra(d);
for(int i=2; i<=n; i++){
    cout<<max(d[i], 0)<<" ";
}

return 0;
}