#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
ifstream fi("input.in");
ofstream fo("fcmc.out");
#define INF 1<<30
#define pb push_back
#define mp make_pair
#define f first
#define s second

int n,m,i,d[50001];
priority_queue< pair< int,int > > q;
vector< pair< int,int > > g[50001];

void readData()
{
    int x,y,c;
    fi >> n >> m;
    for (i=1; i<=m; i++)
    {
        fi >> x >> y >> c;
        g[x].pb(mp(y,c));
    }
}


int main()
{
    
    readData();
    for (i=2; i<=n; i++) d[i]=INF;
    q.push(mp(-d[1],1));
    
    while (!q.empty())
    {
        pair< int,int > u=q.top();  q.pop();
        for (size_t k=0; k<g[u.s].size(); k++)
        {
            pair< int,int> v=g[u.s][k];
            if (d[u.s]+v.s<d[v.f])
            {
                d[v.f]=d[u.s]+v.s;
                q.push(mp(-d[v.f],v.f));
            }
        }
    }
    
    for (i=2; i<=n; i++)
        cout << (d[i]==INF?0:d[i]) << ' ';
    
   return 0;
}