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

using namespace std;

const int NMAX = 50002;
const int DMAX = 2000000001;
int n, m;
int a, b, c;

typedef pair<int, int> ipair;
vector<ipair> g[NMAX];
priority_queue<ipair, vector<ipair>, greater<ipair>> pq;
int dist[NMAX];

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

int main()
{
    fin >> n >> m;
    for(int i=1; i<=m; i++) {
        fin >> a >> b >> c;
        g[a].push_back({ b, c });
    }

    for(int i=1; i<=n; i++)
        dist[i] = DMAX;
    pq.push({ 0, 1 });

    while(!pq.empty()) {
        ipair cr = pq.top();
        pq.pop();
        if(dist[cr.second] < cr.first)
            continue;
        for(ipair vecin : g[cr.second]) {
            int dnou = cr.first + vecin.second;
            if(dist[vecin.first] > dnou) {
                dist[vecin.first] = dnou;
                pq.push({ dnou, vecin.first });
            }
        }
    }

    for(int i=2; i<=n; i++)
        fout << (dist[i] == DMAX ? 0 : dist[i]) << " ";
    return 0;
}