#include<cstdio>
#include<queue>
#include<vector>

using namespace std;

const int N = (1<<16);
const int oo = (1<<30);
const int L = (1<<5);

struct arc
{
	int varf,cost;
};

int m,n,d[N];

struct comp
{
	bool operator()(const int x,const int y)
	{
		return d[x] > d[y];
	}
};

vector<arc> adj[N];
priority_queue <int , vector<int> , comp>  q;
bool s[N];

inline void parse(char* &p,int &x)
{
	while(*p && *p!=' ' && *p!='\n')
	{
		x = x*10 + *p-'0';
		++p;
	}
	++p;
}

void citire()
{
	int x,y,c;
	char s[L],*p;
	scanf("%d%d\n",&n,&m);
	while(m--)
	{
		fgets(s,L,stdin);
		x=y=c=0;
		p=s;
		parse(p,x);
		parse(p,y);
		parse(p,c);
		adj[x].push_back((arc){y,c});
	}
}

void init()
{
	for(int i=1 ; i<=n ; ++i)
		d[i] = oo;
}

void relax(int x)
{
	for(vector<arc>::iterator it=adj[x].begin() ; it!=adj[x].end() ; ++it)
		if(d[x] + it->cost < d[it->varf])
		{
			d[it->varf] = d[x] + it->cost;
			q.push(it->varf);
		}
}

void dijkstra()
{
	int x;
	init();
	d[1] = 0;
	q.push(1);
	while(!q.empty())
	{
		x = q.top();
		q.pop();
		/*
		if(s[x])
			continue;
		*/
		s[x] = true;
		relax(x);
	}
}

void scrie()
{
	for(int i=2 ; i<=n ; ++i)
		printf("%d ",(d[i] == oo ? 0 : d[i]) );
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra();
	scrie();
	return 0;
}