#include <fstream>
#include <vector>
#include <climits>

#define INF INT_MAX/2-1
#define MAXH 50005
using namespace std;

struct nod{
    bool vis;
    int dist;
    int hpos=-1;
    vector< pair<int, int> > v;
};

nod *h[MAXH];
int hcnt;

void update(int pos){
    int cpos = pos/2;

    while(cpos>1 && h[cpos/2]->dist > h[cpos]->dist){
        nod *temp;
        temp = h[cpos/2];
        h[cpos/2] = h[cpos];
        h[cpos] = temp;

        h[cpos/2]->hpos = cpos/2;
        h[cpos]->hpos = cpos;

        cpos /= 2;
    }

}

void add(nod *x){
    h[hcnt] = x;

    int cpos = hcnt;

    while(cpos>1 && h[cpos/2]->dist > h[cpos]->dist){
        nod *temp;
        temp = h[cpos/2];
        h[cpos/2] = h[cpos];
        h[cpos] = temp;

        h[cpos/2]->hpos = cpos/2;
        h[cpos]->hpos = cpos;

        cpos /= 2;
    }

    hcnt++;
}

nod *getMin(){
    if(hcnt==1)return NULL;
    nod *best = h[1];

    int cpos = 1;
    h[1] = h[hcnt-1];

    while(2*cpos+1 < hcnt && ((h[cpos]->dist > h[2*cpos]->dist || h[cpos]->dist > h[2*cpos+1]->dist))){
        if(h[cpos]->dist > h[2*cpos]->dist){
            nod *temp = h[cpos];
            h[cpos] = h[2*cpos];
            h[2*cpos] = temp;

            h[cpos]->hpos = cpos;
            h[2*cpos]->hpos = 2*cpos;

            cpos*=2;
        }
        else {
            nod *temp = h[cpos];
            h[cpos] = h[2*cpos+1];
            h[2*cpos+1] = temp;

            h[cpos]->hpos = cpos;
            h[2*cpos+1]->hpos = 2*cpos+1;

            cpos*=2;
            cpos++;
        }
    }
    hcnt--;
    return best;
}


int main()
{
    hcnt = 1;
    ifstream in("dijkstra.in");
    int n, m;
    in>>n>>m;

    nod w[50001];

    for(int i=1;i<=n;i++){
        w[i].vis = false;
        w[i].dist = INF;
        w[i].hpos = -1;
    }

    for(int i=0;i<m;i++){
        int a, b, d;
        in>>a>>b>>d;
        w[a].v.push_back(make_pair(b, d));
        //w[b].v.push_back(make_pair(a, d));
    }

    nod crt = w[1];
    bool f = true;
    crt.dist = 0;
    int unvis = n;
    while(f){
        for(vector<pair<int, int> >::iterator it = crt.v.begin();it!=crt.v.end();++it){
            if(!w[it->first].vis && it->second + crt.dist < w[it->first].dist){
                w[it->first].dist = it->second + crt.dist;
                if(w[it->first].hpos == -1)add(&w[it->first]);
                else
                    update(w[it->first].hpos);
            }
        }

        crt.vis=true;
        unvis--;
        if(unvis == 0)f = false;
        else crt = *getMin();
    }

    ofstream out("dijkstra.out");
    for(int i=2;i<=n;i++){
        out<<(w[i].dist!=INF?w[i].dist:0)<<" ";
    }
    return 0;
}