#include <fstream>
#include <vector>
#define Inf 2000000000
#define NMax 50005
#define v first
#define c second

using namespace std;
 
vector < pair <int, int> > G[NMax];
int N, D[NMax], Poz[NMax], Heap[NMax], NHeap; 

void Read ()
{
    ifstream fin ("dijkstra.in");

int M;

fin >> N >> M;

for (; M>0; --M)
{

int X, Y, Z;

fin >> X >> Y >> Z;

G[X].push_back (make_pair (Y, Z));

}

fin.close ();

}

 

void Print ()

{

ofstream fout ("dijkstra.out");

for (int i=2; i<=N; ++i)

{

if (D[i]==Inf)

{

D[i]=0;

}

fout << D[i] << " ";

}

fout << "\n";

fout.close ();

}

 

inline void Swap (int X, int Y)

{

int Aux;

Aux=Poz[Heap[X]];

Poz[Heap[X]]=Poz[Heap[Y]];

Poz[Heap[Y]]=Aux;

Aux=Heap[X];

Heap[X]=Heap[Y];

Heap[Y]=Aux;

}

 

void Percolate (int X)

{

int Father=(X>>1);

if (Father>0 and D[Heap[X]]<D[Heap[Father]])

{

Swap (X, Father);

Percolate (Father);

}

}

void Sift (int X)

{

int Son=(X<<1);

if (Son+1<=NHeap and D[Heap[Son+1]]<D[Heap[Son]])

{

++Son;

}

if (Son<=NHeap and D[Heap[Son]]<D[Heap[X]])

{

Swap (X, Son);

Sift (Son);

}

}

 

void Delete (int X)

{

Swap (X, NHeap);

Poz[Heap[NHeap]]=0;

Heap[NHeap]=0;

--NHeap;

Sift (X);

}

 void Initialize (int Start)
 {

NHeap=N;

for (int i=1; i<=N; ++i)

{

D[i]=Inf;

Heap[i]=Poz[i]=i;

}

D[Start]=0;

Swap (1, Start);

}

 

void Dijkstra (int Start)

{

Initialize (Start);

while (NHeap>0)

{

int X=Heap[1];

Delete (1);

for (unsigned i=0; i<G[X].size (); ++i)

{

int V=G[X][i].v;

int C=G[X][i].c;

if (D[X]+C<D[V])

{

D[V]=D[X]+C;

Percolate (Poz[V]);

}

}

}

}

int main()

{

Read ();

Dijkstra (1);

Print ();

return 0;

}