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

#define INF ((1<<29)-1)

using namespace std;

struct d{
    int d, c;
};

struct nod{
    int dist=INF;
    bool vis;
    vector<d> v;
    bool in_queue;
};

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=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;

    int unvis = n;

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

    pq.push(&v[1]);
    v[1].in_queue = true;

    while(unvis){
        crt = pq.top();
        crt->in_queue = false;
        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].dist > crt->dist + c){
                v[d].dist = crt->dist + c;
                if(!v[d].vis){
                    pq.push(&v[d]);
                    v[d].in_queue = true;
                }
            }
        }

        crt->vis = true;
        unvis--;
    }

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