#include <fstream>
#include <vector>
#define NMAx 50100
#define oo (1<<30)
#define Vecin first
#define Cost second
using namespace std;

vector < pair<int,int> > G[NMAx];
int N;

class HEAP {

	#define NMAxHeap NMAx
	#define left(i) (2*i)
	#define right(i) (2*i+1)
	#define father(i) (i/2)
	#define cmp(a,b) (Dist[V[a]]<Dist[V[b]])

	private:
		int V[NMAxHeap],Loc[NMAxHeap],Vf;
    public:
        int Dist[NMAxHeap];
	public:
		HEAP():Vf(0){}
		void push(int,int);
		void pop();
		void update(int,int);
		int top();
		int size();
	private:
		void Up(int);
		void Down(int);

};
void HEAP::Up(int nod) {

	while(nod>1&&cmp(nod,father(nod))) {
		swap(V[nod],V[father(nod)]);
		swap(Loc[V[nod]],Loc[V[father(nod)]]);
		nod=father(nod);
		}

}
void HEAP::Down(int nod) {

	int son;
	do {
		son=0;
		if(left(nod)<=Vf) {

			son=left(nod);
			if(right(nod)<=Vf&&cmp(right(nod),son))
				son=right(nod);

			if(cmp(nod,son))
				son=0;
			}

		if(son) {
			swap(V[nod],V[son]);
			swap(Loc[V[nod]],Loc[V[son]]);
			nod=son;
			}

	}while(son);

}
void HEAP::push(int id,int Val) {

	V[++Vf]=id;
	Dist[id]=Val;
	Loc[id]=Vf;
	this->Up(Vf);

}
void HEAP::pop() {

	V[1]=V[Vf--];
	Loc[V[1]]=1;
	this->Down(1);

}
void HEAP::update(int id,int Val) {

	Dist[id]=Val;
	this->Up(Loc[id]);
	this->Down(Loc[id]);

}
int HEAP::top() {

	return V[1];

}
int HEAP::size() {

	return Vf;

}

HEAP Heap;

void Solve() {

    int i,Nod;

    Heap.push(1,0);
    for(i=2;i<=N;i++)
        Heap.push(i,oo);

    while(Heap.size()) {

        Nod=Heap.top();
        Heap.pop();

        for(i=0;i<G[Nod].size();i++)
            if( Heap.Dist[Nod] + G[Nod][i].Cost < Heap.Dist[G[Nod][i].Vecin] )
                Heap.update(G[Nod][i].Vecin, Heap.Dist[Nod] + G[Nod][i].Cost);

        }

}
void Citire() {

    int i,x,y,c,M;
    ifstream in("dijkstra.in");
    in>>N>>M;

    while(M--) {

        in>>x>>y>>c;
        G[x].push_back(make_pair(y,c));

        }

    in.close();

}
void Afis() {

    ofstream out("dijkstra.out");
    for(int i=2;i<=N;out<<(Heap.Dist[i]<oo?Heap.Dist[i]:0)<<' ',i++);
    out<<'\n';
    out.close();

}
int main() {

    Citire();
    Solve();
    Afis();

	return 0;

}