#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

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

typedef pair<int, int> cuplu;
const int MAXN = 50005;
const int INF = 0x3f3f3f3f;
vector<pair<int, int> > G[MAXN];
priority_queue<cuplu, vector<cuplu>, greater<cuplu> > PQ;
//                                   -sorteaza automat dupa first
int N, M, best[MAXN];
bool marked[MAXN];

void read() {
    int a, b, c;
    fin >> N >> M;
    while (M--) {
        fin >> a >> b >> c;
        G[a].push_back(make_pair(b, c));
    }
}

void dijkstra()  {
    int node;
    best[1] = 0;
    PQ.push(make_pair(0, 1));
    do {
        node = PQ.top().second;
        PQ.pop();
        marked[node] = true;
        vector<cuplu>::iterator it;
        for (it = G[node].begin(); it != G[node].end(); ++it) {
            if (!marked[it->first] && best[it->first] > best[node] + it->second) {
                best[it->first] = best[node] + it->second;
                PQ.push(make_pair(best[it->first], it->first));
            }
        }
    }while (!PQ.empty());
}

inline void write() {
    for (int i = 2; i <= N; ++i)
        fout << (best[i] == INF ? 0 : best[i]) << ' ';
}

int main() {
    read();
    memset(best, INF, sizeof(best));
    dijkstra();
    write();
    fin.close();
    fout.close();
    return 0;
}