#include<iostream>
#include<fstream>
#include<queue>

using namespace std;

#define MAX 50010

int N,M;

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

struct Node
{
	int i,c;
	Node * next;
}*A[MAX];
int viz[MAX],B[MAX];
void add_to_list(int k,int i,int c)
{
	Node *q=new Node;
	q->i=i;
	q->c=c;
	q->next=A[k];
	A[k]=q;
}


class Compare
{
public:
	bool operator ()(int n1,int n2)
	{
		return B[n1]>B[n2];
	}
};

priority_queue<int,vector<int>,Compare> q;

int dijkstra(int n)
{
	int el=1;
	B[el]=0;
	for(int i=1;i<=N;i++)
	{
	  if(i!=el)
	  {
		B[i]=(1<<30);
	    q.push(i);
	  }
	}
	viz[el]=1;

	Node *c=A[el];
	while(!q.empty())
	{
		while(c)
		{
			if(!viz[c->i])
			{
				if(c->c + B[el] <B[c->i])
				{
				   B[c->i]=c->c + B[el];
				   q.push(c->i);
				}
			}
			c=c->next;
		}
		viz[el]=1;
		el=q.top();
		c=A[el];
		q.pop();
	}
	return B[n];
}

int main()
{
   in>>N>>M;
   int k,j,c;
   for(int i=1;i<=M;i++)
   {
	   in>>k>>j>>c;
	   add_to_list(k,j,c);
   }
   int r;
   for(int i=2;i<=N;i++)
   {
	  for(int j=1;j<=N;j++)
		  viz[j]=0;

	   r=dijkstra(i);

	   if(r!=(1<<30))
	    out<<r<<" ";
	   else
		out<<0<<" ";
   }
   in.close();
   out.close();
	return 0;
}