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

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

vector<pair<int , int>> g[50001];
priority_queue <pair<int , int>> d;
int dist[50001];
int vf[50001];
int main()
{
    int n,m;
    cin >>n>>m;
    for (int i = 1; i <= m; i++)
    {
        int a,b,c;
        cin >>a>>b>>c;
        g[a].push_back({b , c});
    }
    for (int i = 1; i <= n; i++)
    {
        dist[i] = 1000000000;
    }
    d.push({0 , 1});
    dist[1] = 0;
    while (d.size() > 0)
    {
        int nod1 = d.top().second;
        d.pop();
        if (vf[nod1] == 0)
        {
            vf[nod1] = 1;
            for (int i = 0; i < g[nod1].size(); i++)
            {
                int nod2 = g[nod1][i].first;
                int val = g[nod1][i].second;
                if (dist[nod2] > dist[nod1] + val)
                {
                    dist[nod2] = dist[nod1] + val;
                    d.push({-dist[nod2] , nod2});
                }
            }
        }
    }
    for (int i = 2; i <= n; i++)
    {
        cout <<dist[i]<<" ";
    }
    return 0;
}