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

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

using namespace std;

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

///Parsare
const int buffsz = (1 << 16) - 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;

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

    queue <pii> dq;
    dq.push(make_pair(0, node));
    costmin[node] = 0;

    for(pii noww; !dq.empty(); ){
        noww = dq.front(); dq.pop();
        for(auto nxt : nextt[noww.y]){
            if(costmin[nxt.x] > noww.x + nxt.y){
                costmin[nxt.x] = noww.x + nxt.y;
                dq.push(make_pair(costmin[nxt.x], nxt.x));
            }
        }
    }

    return;
}

int main(){
    in.tie(nullptr) -> sync_with_stdio(false);
    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;
}