#include <fstream>
#include <queue>
#include <vector>

#define INF ((1<<30))

using namespace std;

struct d{
    int d, c;
};

struct nod{
    int dist;
    bool vis;
    vector<d> v;
    int nr;
};

class Compare{
public:
    bool operator() (nod *a, nod *b){
        return a->dist > b->dist;
    }
};

nod v[50001];

int main(){
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    int n, m;
    in>>n>>m;

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

    for(int i=0;i<m;i++){
        int a, b, c;
        in>>a>>b>>c;

        v[a].v.push_back({b, c});
    }

    priority_queue<nod*, vector<nod*>, Compare> pq;

    nod *crt;
    v[1].dist = 0;

    pq.push(&v[1]);

    while(!pq.empty()){
        crt = pq.top();
        pq.pop();

        for(vector<d>::iterator it = crt->v.begin();it != crt->v.end();++it){
            int d = it->d;
            int c = it->c;

            if(!v[d].vis){
                if(v[d].dist > crt->dist + c){
                    v[d].dist = crt->dist + c;
                    pq.push(&v[d]);
                }
            }
        }

        crt->vis = true;
    }

    for(int i=2;i<=n;i++){
        out<<((v[i].dist==INF )? 0 : v[i].dist)<<" ";
    }
}