#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,g[NMax],c[NMax];
std::pair<int,int> foo;
std::queue< 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;
}

void dijkstra(int x0)
{
    for(i=2;i<=n;++i)d[i]=INF;
    lista.push(std::make_pair(0,x0));
    while(lista.empty()==0)
    {
        foo = lista.front();
        int pmin = foo.second;
        int val = foo.first;
        lista.pop();
        for(i=0;i<g[pmin].size();++i)
        {
            if(d[g[pmin][i]]>val+c[pmin][i])
            {
				d[g[pmin][i]]=val+c[pmin][i];
				lista.push(make_pair(d[g[pmin][i]],g[pmin][i]));
			}
        }
    }
    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);
        g[nod1].push_back(nod2);
        c[nod1].push_back(cost);
    }
    dijkstra(1);
    return 0;
}