#include <fstream>
#include <string.h>
#define dim 50001
#define INF 1 << 28
#include <set>
#include <vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int d[dim],i,j,a,b,c,n,m;
vector < pair <int,int> > G[dim];
multiset < pair <int,int> > heap;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
    }
    memset(d,INF,sizeof(d));
    d[1]=0;
    while(!heap.empty())
    {
        pair <int,int> aux=*heap.begin();
        heap.erase(aux);
        for(vector <pair <int,int> >::iterator it=G[aux.first].begin();it!=G[aux.first].end();it++)
        {
            if(d[aux.first]+it->second<d[it->first])
            {
                heap.erase(make_pair(it->first,d[it->first]));
                d[it->first]=d[aux.first]+it->second;
                heap.insert(make_pair(it->first,d[it->first]));
            }
        }
    }
    for(i=2;i<=n;i++)
        if(d[i]!=INF)
            fout<<d[i]<<" ";
        else
            fout<<0<<" ";
    return 0;
}