#include<fstream>
#include<vector>
#define MaxBuffer 8192
using namespace std;
int n,m,vf=1;
const int INF=1<<30;
char buffer[MaxBuffer];
int bufferIndex=-1;
int sol[50010],heap[50010],unde[50010];
vector <unsigned short> cost[50010],vecin[50010];
inline int left(int i) {return 2*i;}
inline int right(int i) {return 2*i+1;}
inline int father(int i) {return i/2;}
inline int cmp(int a,int b) {return sol[a]>sol[b];}
void up(int i)
{while(i>1&&cmp(heap[father(i)],heap[i]))
	{swap(heap[i],heap[father(i)]);
	swap(unde[heap[i]],unde[heap[father(i)]]);
	i=father(i);
	}
}
void down(int i)
{int son;
do 	{son=0;
	if(left(i)<=vf)
		{son=left(i);
		if(right(i)<=vf&&cmp(heap[left(i)],heap[right(i)]))
			son=right(i);
		if(cmp(heap[son],heap[i]))
			son=0;
		}
	if(son)
		{swap(heap[son],heap[i]);
		swap(unde[heap[son]],unde[heap[i]]);
		i=son;
		}
	} while(son) ; 
}
inline void Read( istream& in,  int& x )
{
      if( -1 == bufferIndex )
      {
          in.read( buffer, MaxBuffer );
          bufferIndex=0;    
      }
      while( buffer[bufferIndex] < '0' || buffer[bufferIndex] > '9' ) 
           if( ++bufferIndex == MaxBuffer )
           {
              bufferIndex=0;
              in.read( buffer, MaxBuffer );
           }
     for( x=0; buffer[bufferIndex] >= '0' && buffer[bufferIndex] <= '9'; )
     {
          x=x*10+buffer[bufferIndex]-'0';
          if( ++bufferIndex == MaxBuffer )
          {
              bufferIndex=0;
              in.read( buffer, MaxBuffer );
          }
     }
}
void citire()
{int i,y,x,c;
ifstream in("dijkstra.in");
Read(in, n); Read(in, m);
for(i=0;i<m;i++)
	{ Read(in, x); Read(in, y); Read(in, c);
 	vecin[x].push_back(y);
	cost[x].push_back(c);
	}

}
void dijkstra()
{int nod=1,vec,p;
unsigned int j;
//for(i=2;i<=n;sol[i]=INF,i++);
heap[1]=1;unde[1]=1;
while(vf>0)
	{nod=heap[1];unde[nod]=-1;
	heap[1]=heap[vf--];
	unde[heap[1]]=1;
	down(1);
	p=vecin[nod].size();
	for(j=0;j<p;j++)
		{vec=vecin[nod][j];
		 if(unde[vec]==0)
		     heap[++vf]=vec,unde[vec]=vf,sol[vec]=sol[nod]+cost[nod][j],up(vf);
		 else if(sol[vec]>sol[nod]+cost[nod][j])
				{sol[vec]=sol[nod]+cost[nod][j];
				up(unde[vec]);
				}
		}
	}
}
int main()
{
citire();
dijkstra();
ofstream out("dijkstra.out");
for(int i=2;i<=n;i++)
	{//if(sol[i]==INF)
		//sol[i]=0;
	out<<sol[i]<<" ";
	}
out<<'\n';

return 0;
}