#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>

using namespace std;

const int NMAX = 5e4 + 5, MMAX = 2e5 + 5e4 + 5;

struct coord
{
    int val, cost;

    bool operator < (const coord &other)const
    {
        return cost>other.cost;
    }
};

int n, m, dist[NMAX];
bool viz[NMAX];
vector<pair<int, int>> v[NMAX];
priority_queue<coord> q;

void bfs()
{
    q.push({1, 0});

    while(!q.empty())
    {
        int nodval = q.top().val, nodcost = q.top().cost;
        q.pop();

        if(!viz[nodval])
        {
            viz[nodval] = true;
            dist[nodval] = nodcost;
            
            for(auto nod : v[nodval])
            {
                if(!viz[nod.first])
                    q.push({nod.first, nodcost + nod.second});
            }
        }
    }

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

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        cin >> x >> y >> cost;
        v[x].push_back({y, cost});
    }
    
    bfs();
}