#include <cstdio>
#include <queue>
#include <vector>
#define source 1
#define NMAX 50001
#define INF (1<<21)

using namespace std;

FILE *fin = fopen("dijkstra.in", "r");
FILE *fout = fopen("dijkstra.out", "w");

int N, M;
int D[NMAX], U[NMAX];

class cmp
{
    public:
    inline bool operator()(const int &x, const int &y) {
        return D[x] > D[y];
    }
};

vector< pair<int, int> > G[NMAX];
priority_queue<int, vector<int>, cmp> Q;

void ReadData() {
    int i, u, v, cost;
    fscanf(fin, "%d %d", &N, &M);
    for(i = 1; i <= M; ++ i) {
        fscanf(fin, "%d %d %d", &u, &v, &cost);
        G[u].push_back(make_pair(v, cost));
    }
}

void Init() {
    for(int i = 2; i <= N; ++ i)
        D[i] = INF;
}

void Dijkstra() {
    Init();
    Q.push(source);
    vector< pair<int, int> >::iterator it;
    while(!Q.empty()) {
        int nod = Q.top();
        Q.pop();
        U[nod] = 0;
        for(it = G[nod].begin(); it != G[nod].end(); ++ it)
            if(D[it->first] > D[nod] + it->second) {
                D[it->first] = D[nod] + it->second;
                if(!U[it->first]) {
                    Q.push(it->first);
                    U[it->first] = 1;
                }
            }
    }
}

void ShowData() {
    for(int i = 2; i <= N; ++ i)
        if(D[i] == INF)
            fprintf(fout, "0 ");
        else
            fprintf(fout, "%d ", D[i]);
}

int main() {
    ReadData();
    Dijkstra();
    ShowData();
    return 0;
}