#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");


///Parsare
const int buffsz = (1 << 14) - 1;
char buffer[buffsz]; int idx = buffsz - 1;

char getnxtchar(){
    idx++;
    if(idx >= buffsz){
        in.read(buffer, buffsz);
        idx = 0;
    }
    return buffer[idx];
}

int readint(){
    int x = 0; char _t;
    for(_t = getnxtchar(); isspace(_t); _t = getnxtchar());
    for(; '0' <= _t && _t <= '9'; _t = getnxtchar())
        x = 10 * x + _t - '0';
    return x;
}

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(){
    n = readint();
    m = readint();
    for(int i = 1; i <= m; i++){
        a = readint(); b = readint(); cst = readint();
        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;
}