#include<fstream>
#include<set>
#include<vector>
#define maxn 50001
#define inf 99999999
#define baga push_back
#define maxm 250001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
set <pair <int,int> > S;
int n,m,e1,e2,c;
vector<int> G[maxn],C[maxn];
vector<int> d(maxn);
void dijkstra(){
    int val,nod;

    for(int i=2;i<=n;++i)
        d[i]=inf;
    S.insert(make_pair(0,1)); //0-cost, 1-nodul
    while(S.empty()==0){
        val= (*S.begin()).first;
        nod= (*S.begin()).second;
        S.erase(*S.begin());
        for(int i=0;i<G[nod].size();++i){
            if(d[G[nod][i]]>val+C[nod][i]){
                d[G[nod][i]]=val+C[nod][i];
                S.insert(make_pair(d[G[nod][i]],G[nod][i]));
            }
        }
    }
}
int main (){
    f>>n>>m;

    for(int i=1;i<=m;++i){
        f>>e1>>e2>>c;
        G[e1].baga(e2);
        C[e1].baga(c);
    }
    dijkstra();
    for(int i=2;i<=n;++i)
        if(d[i]!=inf)
            g<<d[i]<<" ";
    return 0;
}