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

ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");

vector<pair<int , int>> g[50001];
int viz[50001];
int dist[50001];

void dijkstra (int x)
{
    priority_queue<pair<int , int>> d;
    d.push({0 , x});
    dist[x] = 0;
    while (d.size() > 0)
    {
        int nod1 = d.top().second;
        d.pop();
        if (viz[nod1] == 0)
        {
            viz[nod1] = 1;
            for (int i = 0; i < g[nod1].size(); i++)
            {
                int nod2 = g[nod1][i].first;
                int cost = g[nod1][i].second;
                if (dist[nod2] > cost + dist[nod1])
                {
                    dist[nod2] = cost + dist[nod1];
                    d.push({-dist[nod2] , nod2});
                }
            }
        }
    }
}

int main()
{
    int n,m;
    cin >>n>>m;
    for (int i = 1; i <= m; i++)
    {
        int x,y,val;
        cin >>x>>y>>val;
        g[x].push_back({y , val});
    }
    for (int i = 1; i <= n; i++)
    {
        dist[i] = m * 20000;
    }
    dijkstra(1);
    for (int i = 2; i <= n; i++)
    {
        cout <<dist[i]<<" ";
    }
    return 0;
}