#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <utility>
#include <queue>
#define MAXn 50000
#define MAXm 250000
#define inf 1000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,i,j,x,y,z,dist[MAXn];

vector<pair<int,int> > muchii[MAXn];
set<pair<int,int> > s;
priority_queue<pair<int,int> > q;
bool viz[MAXn];

void citire()
{
    f>>n>>m;
    for(i=1; i<=m; i++)
        f>>x>>y>>z, muchii[x].push_back(make_pair(y,z));
}

void dijkstra()
{
    for(i=1; i<=n; i++)
        dist[i] = inf;
    q.push(make_pair(0,1));
    dist[1]=0;
    while(q.size())
    {
        z = q.top().first;
        y = q.top().second;
        q.pop();
        if(!viz[y])
            for(i=0; i<muchii[y].size(); i++)
                if(dist[muchii[y][i].first] > muchii[y][i].second + z)
                    dist[muchii[y][i].first] = muchii[y][i].second + z, q.push(make_pair(dist[muchii[y][i].first], muchii[y][i].first)), viz[y] = true;;
    }
    /*
    s.insert(make_pair(0,1));
    while(s.size())
    {
        y = (*s.begin()).second;
        z = (*s.begin()).first;
        s.erase(s.begin());
        for(i=0; i<muchii[y].size(); i++)
            if(dist[muchii[y][i].first] > muchii[y][i].second + z)
            dist[muchii[y][i].first] = muchii[y][i].second + z, s.insert(make_pair(dist[muchii[y][i].first],muchii[y][i].first));
    }*/
}

int main()
{
    citire();
    dijkstra();
    for(i=2; i<=n; i++)
        if(dist[i]!=inf)
            g << dist[i] << ' ';
        else
            g << "0 ";
    return 0;
}