#include <fstream>
#include <vector>
#include <iomanip>

#define NMAX 50000
#define infinite 1000000
#define mp make_pair
#define pb push_back

using namespace std;

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

int N,M, d[NMAX];
vector <int> G[NMAX], C[NMAX];

typedef int Heap[NMAX];

inline int father(int node){return node/2;}

inline int left_son(int node){return 2*node;}

inline int right_son(int node){return 2*node+1;}

inline int head(Heap H){return H[1];}

void print(Heap H, int N, int K, int D)
{
	if(H[K])
	{
		if(right_son(K)<=N)
			print(H, N, right_son(K), D+1);
		fout<<setw(4*D)<<"";
		fout<<d[H[K]]<<endl;
		if(left_son(K)<=N)
			print(H, N, left_son(K), D+1);
		
	}
}

void down(Heap H, int N, int K) // Descendenta nodului pana la stabilirea echilibrului
{
    int son,a,b;
    do{
        son=0;
        a=left_son(K);
        b=right_son(K);
        
        if(a<=N){
            son=a;
            if(b<=N && d[H[b]]<=d[H[a]]) // Comparam valorile din vectorul de valori
                son=b;
            // Alegem fiul cel mai mare, in limita N.
            if(d[H[son]]>=d[H[K]]) //Daca chiar fiul cel mai mic este mai mare, nu este nevoie de a cerne mai departe
                son=0;
        }
        
        // Daca exista un fiu cu o valoare mai mica interschimbam
        
        if(son)
        {
            swap(H[K], H[son]);
			K=son; // Cernem mai departe recursiv
        }
    }while(son);
}

void up(Heap H, int K, int N) //Urcam nodul pana se stabileste echilibrul
{
    int key=H[K];
    
    while(K>1 && d[key]<d[H[father(K)]]) // Urcam in arbore recursiv
    {
        H[K]=H[father(K)];
        K=father(K);
    }
    
    H[K]=key; // La ultimul nod urcat atribuim valoarea nodului initial
}

void build_heap(Heap H, int N) // Sortam heap-ul
{
    for(int i=N/2; i>0; --i)
        down(H,N,i);
}

void erase(Heap H, int& N, int K) // Stergerea unui element in O(logn), K - pozitia K in Heap
{
	H[K]=H[N];
    --N;
    if(K>1 && d[H[K]]<d[H[father(K)]])
        up(H, N, K);
    else
        down(H, N, K);
}

void insert(Heap H, int& N, int key)
{
    H[++N]=key;
    up(H, N, N);
}

Heap A; int K; // Heap vector and heap size

void fullDijkstra()
{
    int val,x;
    
    for(int i=2; i<=N; ++i)
        d[i]=infinite;
    
    insert(A, K, 1);
    
    while(K)
    {
        x = head(A);
        erase(A, K, 1);
        for(unsigned i=0; i<G[x].size(); ++i) // Relaxăm nodul x
            if(d[G[x][i]]>d[x]+C[x][i])
                d[G[x][i]]=d[x]+C[x][i], insert(A, K, G[x][i]);
    }
}

int main()
{
    fin>>N>>M;
    
    int x,y,c;
    while(M--)
    {
        fin>>x>>y>>c;
        G[x].pb(y);
        C[x].pb(c);
    }
    fullDijkstra();
    for(int i=2; i<=N; ++i)
        fout<<(d[i] == infinite ? 0 : d[i])<<" ";
    
    return 0;
}