#include <iostream>
#include<fstream>
#include<vector>
#include<limits>
#include<algorithm>
#include<queue>
#define INF numeric_limits<int>::max()
using namespace std;

ifstream f("djikstra.in");
ofstream g("djikstra.out");

vector<int> d;
vector< vector< pair< int,int> > > a;
priority_queue< pair<int,int> > q;
int n;

void citire()
{
    int m,x,y,c;
    f>>n>>m;
    a=vector<vector<pair<int,int> > > (n+1);
    d=vector<int> (n+1,INF);
    while(m)
    {
        f>>x>>y>>c;
        a[x].push_back(make_pair(y,c));
        m--;
    }
}

void djikstra(int k)
{
    d[k]=0;
    q.push(make_pair(0,k));
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        for(vector<pair<int,int> >::iterator i=a[x].begin();i!=a[x].end();i++)
            if( d[x]+i->second < d[i->first])
            {
                d[i->first]=d[x]+i->second;
                q.push(make_pair(-d[i->first],i->first));
            }
    }
}

void write_it()
{
    int i;
    for(i=2;i<=n;i++)
    {
        if(d[i]==INF) g<<"0 ";
        else g<<d[i]<<" ";
    }
}

int main()
{
    citire();
    djikstra(1);
    write_it();
    return 0;
}