#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <pair<int,int> > v[250000];
priority_queue <pair<int, int> > q;

int n, m, viz[50001], cost[50001];

void citire()
{
    fin>>n>>m;
    for(int i=2; i<=n; i++)
        viz[i] = INF;

    for(int i=1; i<=m; i++)
    {
        int nod1, nod2, cost;
        fin >> nod1 >> nod2 >> cost;
        v[nod1].push_back(make_pair(nod2,cost));
    }
}

void dijk()
{
    q.push(make_pair(0, 1));
    while(!q.empty())
    {
        int x, y;
        x = -q.top().first;
        y = q.top().second;
        q.pop();
        for(vector<pair<int, int> > :: iterator it=v[y].begin(); it != v[y].end(); ++it)
            if(x + it->second < viz[it->first])
            {
                viz[it->first] = x + it->second;
                q.push(make_pair(-(it->second), it->first));
            }

    }
}

void afisare()
{
    for(int i = 2; i <= m; i++)
    {
        cout<<i <<" ";
        for(vector<pair<int,int> > ::iterator it = v[i].begin(); it != v[i].end(); ++it)
           cout<< it->first<<" "<< it->second<<"; ";
        cout<<"\n";
    }
}

int main()
{
    citire();
    dijk();
    for(int i=2; i<=n; i++)
        fout<<viz[i]<<" ";

    return 0;
}