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

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

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

    for(pii noww; !dq.empty(); ){
        noww = dq.top(); 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>>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;
}