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

using namespace std;

const int NMAX = 50001;
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];

int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin >> n >> m;
    for(int i=1; i<=m; i++) {
        cin >> a >> b >> c;
        g[a].push_back({ b, c });
    }

    for(int i=2; 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)
            dist[cr.second] = cr.first;
        for(ipair vecin : g[cr.second]) {
            int dnou = cr.first + vecin.second;
            if(dist[vecin.first] > dnou)
                pq.push({ dnou, vecin.first });
        }
    }

    for(int i=2; i<=n; i++)
        cout << dist[i] << " ";
    return 0;
}