#include<cstdio>
#include<vector>
using namespace std;
const int N=50000;
int min2(int a,int b){
    if(a<b)
        return a;
    return b;
}

class Edge{
    public:
        int v,c;
        Edge(){
        }
        Edge(int vv,int cc){
            v=vv;
            c=cc;
        }
        bool operator<(const Edge&e)const{
            return c<e.c;
        }
};

class Heap{
    public:
        Edge v[N+1];
        int l;
        void build(){
            l=0;
        }
        bool isEmpty(){
            return l==0;
        }
        Edge top(){
            return v[1];
        }
        void push(Edge e){
            v[++l]=e;
            pos[e.v]=l;
            upHeap(l);
        }
        void pop(int x){
            int p=pos[x];
            if(p==0)
                return;
            v[p]=v[l];
            pos[v[l].v]=p;
            pos[x]=0;
            l--;
            upHeap(p);
            downHeap(p);
        }
    private:
        int pos[N+1];
        void upHeap(int p){
            if(p<=1)
                return;
            if(v[p]<v[p/2]){
                change(p,p/2);
                upHeap(p/2);
            }
        }
        void downHeap(int p){
            if(p*2+1<=l){
                if(min2(v[p*2].c,v[p*2+1].c),v[p].c)
                    if(v[p*2]<v[p*2+1]){
                        change(p,p*2);
                        downHeap(p*2);
                    }
                    else{
                        change(p,p*2+1);
                        downHeap(p*2+1);
                    }
            }
            else
                if(p*2<=l)
                    if(v[p*2]<v[p]){
                        change(p,p*2);
                        downHeap(p*2);
                    }
        }
        void change(int p1,int p2){
            Edge aux=v[p1];
            v[p1]=v[p2];
            v[p2]=aux;
            pos[v[p1].v]=p1;
            pos[v[p2].v]=p2;
        }
};

int n,m;
Heap h;
int dist[N+1];
vector<Edge>g[N+1];
void dijkstra(int node){
    h.build();
    h.push(Edge(node,0));
    dist[1]=0;
    while(!h.isEmpty()){
        Edge dad=h.top();
        h.pop(dad.v);
        for(int i=0;i<g[dad.v].size();i++){
            Edge son=g[dad.v][i];
            if(son.v!=1&&(dist[son.v]==-1||dist[dad.v]+son.c<dist[son.v])){
                h.pop(son.v);
                h.push(son);
                dist[son.v]=dist[dad.v]+son.c;
            }
        }
    }
}
void init(){
    for(int i=1;i<=n;i++)
        dist[i]=-1;
}
int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    init();
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        g[x].push_back(Edge(y,z));
    }
    dijkstra(1);
    for(int i=2;i<=n;i++)
        if(dist[i]==-1)
            printf("0 ");
        else
            printf("%d ",dist[i]);
    return 0;
}