///complexity: O(M*logN)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

#define limn 50010
#define inf 2e9

int n,m;
vector < pair <int, int> > G[limn];
priority_queue < pair < int, int> > pq; ///first -> the cost, second -> the node
int path[limn]; ///path[i] = shortest path from node 1 to i

///dijkstra from node source
void dijkstra(int source)
{
    int cost, node;
    for(int i=1; i<=n; i++)
        path[i] = inf;
    path[source] = 0;
    pq.push({0, source});
    while(!pq.empty())
    {
        node = pq.top().second;
        cost = -pq.top().first;
        pq.pop();
        if(path[node] != inf && path[node] != 0)
            continue;
        path[node] = cost;
        for(auto it:G[node])
            if(path[it.first] > cost + it.second)
                pq.push({-(cost + it.second), it.first});
    }

}

int main()
{
    int x, y, c;

    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y>>c;
        G[x].push_back({y,c});
    }
    dijkstra(1);

    for(int i=2; i<=n; i++)
        if(path[i] != inf)
            fout<<path[i]<<' ';
        else fout<<0<<' ';

    fout.close();
    return 0;
}