#include<fstream>
#include<vector>
#include<list>
#include<algorithm>

#define NMAX  50001
#define INF 250000010
#define DIM 25900000

using namespace std;

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

struct minim
{
	int c, o;
};
struct muchie
{
	int v, c;
};

vector<minim> heap(DIM);
vector<int> d(NMAX, INF);
vector<bool> vz(NMAX);
vector<muchie> a[NMAX];

/*minim heap[DIM];
int d[NMAX];
bool vz[NMAX];*/
int n, m, nh=1;

void citeste()
{
	int i, x, y, c; 
	muchie r;
	f>>n>>m;
	for(i=1; i<=m ; ++i)
	{
		f>>x>>y>>c;
		r.v=y; r.c=c;
		a[x].push_back(r);
	}
	for (i=1; i<=n; ++i) d[i]=INF;
}
void insert(int f)
{
    int t=f/2;
    while (heap[t].c>heap[f].c)
    {
        swap(heap[t], heap[f]);
        f=t; t=f/2;
    }
}
void coboara()
{
    int t=1, imn, f;
    while ( (t*2<=nh && heap[t*2].c<heap[t].c) || (t*2+1<=nh && heap[t*2+1].c<=heap[t].c) )
    {
        f=t*2; imn=f;
        if (f+1<=nh && heap[f].c>heap[f+1].c) imn=f+1;
		swap(heap[imn], heap[t]);
        t=imn;
    }
}

void djk()
{
	int nr=0, i;
	minim r, q;
	muchie p;
	heap[1].c=0; heap[1].o=1;
	while (nr<n && nh>0)
	{
		r=heap[1];
		vz[r.o]=1;
		for (i=0; i!=a[r.o].size(); ++i)
		{
			p=a[r.o][i];
			if (!vz[p.v] && d[p.v]>r.c+p.c)
			{
				d[p.v]=r.c+p.c;
				q.c=d[p.v]; q.o=p.v;
				heap[++nh]=q;
				insert(nh);
			}
		}
		heap[1]=heap[nh--];
		coboara();
		++nr;
	}
	for (i=2; i<=n; ++i)
		if (d[i]==INF) g<<"0 ";
		else g<<d[i]<<" ";
}

int main()
{
	citeste();
	djk();
	f.close();
	g.close();
	return 0;
}