#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define NM 50002
using namespace std;

vector <pair <int, int> > gr[NM];

set <pair <int, int> > djk;

set <pair <int, int> > :: iterator it;
pair <int, int> vit;

int n, m, a, b, c, v[NM], cm[NM];

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

void dijkstra (int node)
{
    int t;
    int i;
    djk.insert(make_pair(0, node));
    while(!djk.empty())
    {
        it = djk.begin();
        djk.erase(it);
        vit = *it;
        t = vit.second;
        if(v[t] == 0)
        {
            v[t] = 1;
            cm[t] = vit.first;
            for(i = 0; i < gr[t].size(); i++)
            {
                pair <int, int> k;
                k = gr[t][i];
                if(v[k.first] == 0)
                {
                    djk.insert(make_pair(cm[t] + k.second, k.first));
                }
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> a >> b >> c;
        gr[a].push_back(make_pair(b, c));
    }
    dijkstra(1);
    for(int i = 2; i <= n; i++)
        fout << cm[i] << " ";
    return 0;
}