#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX=5e4;

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

struct edge{
    int y;
    int cost;
};

vector <edge> g[NMAX+1];

int heap[NMAX+1],heap_pos[NMAX+1];
int dist[NMAX+1];
bool found[NMAX+1];
int heap_size;

void heap_swap(int node_1,int node_2){
    swap(heap_pos[heap[node_1]],heap_pos[heap[node_2]]);
    swap(heap[node_1],heap[node_2]);
}

void heap_up(int pos){
    while(pos>1 && dist[heap[pos]]<dist[heap[pos >>1]])
    {
        heap_swap(pos,pos>>1);
        pos>>=1;
    }
}

void heap_down(int pos){
    int st,dr,best;
    while((pos<<1)<=heap_size){
        st=(pos<<1);
        dr=st+1;
        best=st;
        if(dist[heap[dr]]<dist[heap[st]] && dr<=heap_size)
            best=dr;
        if(dist[heap[pos]] > dist[heap[best]])
            heap_swap(pos,best);
        else
            break;
        pos=best;
    }
}

void heap_add(int node){
    heap[++heap_size]=node;
    heap_pos[node]=heap_size;

    heap_up(heap_size);
}

void heap_erase(int node){
    int pos_index=heap_pos[node];
    heap_swap(pos_index,heap_size);
    --heap_size;

    //heap_up(pos_index); - stergere varf
    heap_down(pos_index);
}

void heap_update(int node){
    heap_up[heap_pos[node]];
}

void djikstra(int start_pos){
    found[start_pos]=1;
    heap_add(start_pos);

    int x,y,cost;
    while(heap_size>0){
        x=heap[1];
        heap_erase(heap[1]);
        for(const edge &e:g[x]){
            y=e.y;
            cost=e.cost;

            if(!found[y]){
                found[y]=true;
                dist[y]=dist[x]+cost;
                heap_add(y);
            }
            else if(dist[x]+cost<dist[y])
            {
                dist[y]=dist[x]+cost;
                heap_update(y);
            }
        }
    }
}

int main()
{
    int n,m,x,y;
    edge aux;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>aux.cost;
        aux.y=y;
        g[x].push_back(aux);
        //aux.y=x;
        //g[y].push_back(aux);
    }

    djikstra(1);

    for(int node=2;node<=n;node++)
        fout<<dist[node]<<" ";
    fout<<"\n";

    return 0;
}