#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct compare{
   bool operator()(pair<int,int> p1, pair<int,int> p2){
        return p1.second>p2.second;
   }
};

priority_queue< pair<int,int> , vector< pair<int,int> > , compare >pq;
vector< pair<int,int> >v[50001];
int n, m, a, b, cost, x, dx, d[50001], viz[50001];

int main()
{
    in>>n>>m;
    for(int i=2;i<=n;++i) d[i]=INF;
    for(int i=1;i<=m;++i)
    {
        in>>a>>b>>cost;
        v[a].push_back( make_pair(b,cost) );
    }

    pq.push(make_pair(1,0));

    while(!pq.empty())
    {
        while(!pq.empty() && viz[pq.top().first])
            pq.pop();
        if(pq.empty())
            break;
        x=pq.top().first;
        viz[x]=1;
        pq.pop();

        for(int i=0; i<v[x].size(); ++i)
        {
            if(d[v[x][i].first] > d[x] + v[x][i].second){
                d[v[x][i].first] = d[x] + v[x][i].second;
                pq.push(make_pair(v[x][i].first, d[v[x][i].first]));
            }
        }
    }

    for(int i=2; i<=n; ++i)
        if(d[i]==INF) out<<"0 ";
        else out<<d[i]<<' ';

    return 0;
}