#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int NMAX=50002, inf=(1<<20);
vector< pair<int, int> > g[NMAX];


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

    vector<int> dist(n+1, inf);
    dist[1]=0;
    priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > heap;
    heap.push(make_pair(0, 1));

    while(!heap.empty())
    {
        int d=heap.top().first;
        int u=heap.top().second;
        heap.pop();

        if(d>dist[u])
            continue;

        for(int i=0; i<g[u].size(); i++)
        {
            int v=g[u][i].first;
            int duv=g[u][i].second;
            if(dist[v]>dist[u]+duv)
                dist[v]=dist[u]+duv;
            heap.push(make_pair(dist[v], v));

        }
    }

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