#include <cstdio>
#include <vector>
#include <climits>
#include <utility>
#define N 50010


using namespace std;


const int INF=INT_MAX;
int n,m;
vector<pair<int,int> > arcs[N];
int d[N];
int pred[N];

int readInt()
{
	int n=0;
	char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0' && c<='9')
	{
		n=(n<<1)+(n<<3) +c-'0';
		c=getchar();
	}
	return n;
}

void Read()
{
	freopen("dijkstra.in","r",stdin);
	int a,b,d;
	n=readInt();
	m=readInt();
	for(int i=0;i<m;++i)
	{
		a=readInt();
		b=readInt();
		d=readInt();
		arcs[a].push_back(make_pair(b,d));
	}
}

void Dijkstra(int s)
{

}

bool BellmanFord(int s)
{
	for(int i=1;i<=n;++i)
	{
		pred[i]=0;
		d[i]=INF/2;
	}
	d[s]=0;
	vector<pair<int,int> >::iterator it;
	for(int i=1;i<=n;++i)
	{
			for(it=arcs[i].begin();it!=arcs[i].end();++it)
			{
				if(d[it->first]>d[i]+it->second)
				{
					d[it->first]=d[i]+it->second;
					pred[it->first]=i;	
				}
			}
	}
	for(int i=1;i<=n;++i)
	{
		for(it=arcs[i].begin();it!=arcs[i].end();++it)
		{
			if(d[it->first]>d[i]+it->second)
			{
				return false;
			}
		}
	}
	return true;
}

void Write()
{
	freopen("dijkstra.out","w",stdout);
	for(int i=2;i<=n;++i)
	{
		if(pred[i]==0)
		{
			printf("0 ");
		}
		else
		{
			printf("%d ",d[i]);
		}
	}
	printf("\n");
}

int main()
{
	Read();
	BellmanFord(1);
	Write();
	return 0;
}