#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

ifstream F("dijkstra.in");
ofstream G("dijkstra.out");

const int N = 50010;

struct cmp {
    bool operator () (pair<int,int> x,pair<int,int> y)
    {
        return x.second > y.second;
    }
};

priority_queue<pair<int,int>,vector<pair<int,int> >,cmp> q;

int n,m,d[N];
vector< pair<int,int> > v[N];

int main()
{
    F>>n>>m;
    for (int i=1,x,y,c;i<=m;++i)
    {
        F>>x>>y>>c;
        v[x].push_back( make_pair(y,c) );
    }

    memset(d,0x3f,sizeof(d));
    d[1] = 0;
    q.push( make_pair(1,0) );
    while ( !q.empty() )
    {
        int x = q.top().first;
        int c = q.top().second;
        q.pop();

        for (int i=0;i<int(v[x].size());++i)
        {
            int y = v[x][i].first;
            int ct = v[x][i].second + c;

            if ( ct < d[y] )
            {
                d[y] = ct;
                q.push( make_pair(y,ct) );
            }
        }
    }
    for (int i=2;i<=n;++i)
        G<<d[i]<<' ';
    G<<'\n';
}