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

#include <utility>
#define x first
#define y second

#pragma GCC optimize("O3", "unroll-loops")

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

typedef pair <int, int> pii;
typedef vector <pii> vpii;
const int nmax = 50000;
int n, m; vpii nextt[nmax + 2];
int costmin[nmax + 2], a, b, cst;

struct nodetype{
    int nd;
    nodetype() : nd(0) {};
    nodetype(int node) : nd(node) {};
    bool operator < (const nodetype obj) const {
        return costmin[nd] > costmin[obj.nd];
    }
};

void dijkstra(int node){
    for(int i = 1; i <= n; i++)
        costmin[i] = (1 << 30);

    priority_queue <nodetype> dq;
    costmin[node] = 0; dq.push(nodetype(node));

    for(int noww; !dq.empty(); ){
        noww = dq.top().nd; dq.pop();
        for(auto nxt : nextt[noww]){
            if(costmin[nxt.x] > costmin[noww] + nxt.y)
                costmin[nxt.x] = costmin[noww] + nxt.y, dq.push(nodetype(nxt.x));
        }
    }

    return;
}

int main(){
    in>>n>>m;
    for(int i = 1; i <= m; i++){
        in>>a>>b>>cst;
        nextt[a].push_back(make_pair(b, cst));
    }

    dijkstra(1);

    for(int i = 2; i <= n; i++)
        out<<((costmin[i] == (1 << 30)) ? 0 : costmin[i])<<" ";
    out<<"\n";

    return 0;
}