#include <fstream>
#include <queue>
#include <vector>
#include <list>
#include <algorithm>
#define NMax 50002
#define INF 1<<30
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,i,nod1,nod2,cost,d[NMax];
std::vector<int> viz;
std::pair<int,int> foo;
class Compare
{
    public:
    bool operator()(std::pair<int,int> t1, std::pair<int,int> t2)
    {
       if( t1.second > t2.second ) return true;
       return false;
    }
};
std::priority_queue< std::pair<int,int> , std::vector< std::pair<int,int> > , Compare > coada;
std::list< std::pair<int,int> > lista;

struct graf
{
    int nod,cost;
    graf *next;
};
graf *a[NMax];
void add(int where,int what,int cost)
{
    graf *newid = new graf;
    newid->nod = what;
    newid->cost = cost;
    newid->next = a[where];
    a[where] = newid;
}
bool Cmp(std::pair<int,int> t1, std::pair<int,int> t2)
{
    return t1.second < t2.second;
}
bool Eliminare(std::pair<int,int> t1)
{
    if(viz[t1.first-1]==1)return true;
    return false;
}
void dijkstra(int x0)
{
    for(i=2;i<=n;++i)d[i]=INF;
    lista.push_front(std::make_pair(x0,0));
    int pmin = 0,minim = INF;
    /*for(int j=1;j<=n;++j)
    {
        //lista.sort(Cmp);
        do
        {
            foo = lista.front();
            pmin = foo.first;
            if(viz[pmin-1]==1)lista.pop_front();
        }while(!(viz[pmin-1]==0||lista.size()==0));
        if(lista.size()==0)break;
        lista.pop_front();

        viz[pmin-1] = 1;
        graf *t = a[pmin];
        while(t)
        {
            if(d[t->nod] > d[pmin] + t->cost)
            {
                d[t->nod] = d[pmin] + t->cost ;
                lista.push_front(std::make_pair(t->nod,d[t->nod]));
            }
            t = t->next;
        }
    }*/
    while(lista.empty()==0)
    {
        foo = lista.front();
        pmin = foo.first;
        lista.pop_front();
        graf *t = a[pmin];
        while(t)
        {
            if(d[t->nod] > d[pmin] + t->cost)
            {
                d[t->nod] = d[pmin] + t->cost ;
                lista.push_front(std::make_pair(t->nod,d[t->nod]));
            }
            t = t->next;
        }
    }
    for(i=2;i<=n;++i)
    {
        if(d[i]==INF)fout<<"0 ";
        else fout<<d[i]<<" ";
    }
}

int main()
{
    fin>>n>>m;
    viz.resize(n);
    for(i=1;i<=m;++i)
    {
        fin>>nod1>>nod2>>cost;
        add(nod1,nod2,cost);
    }
    dijkstra(1);
    return 0;
}