#include <bits/stdc++.h>
#define LIM 1<<17
#define INF 2100000000
#define nod first
#define cost second
/// TONI BO$$ was here
/// #MLC

using namespace std;
char BUF[LIM];
int poz;

inline char getChar(){
    poz++;
    if(poz>=LIM){
    	fread(BUF,LIM,1,stdin);
    	poz=0;
    }
    return BUF[poz];
}

inline int getNr(){
    int r=0, semn=1;
    char ch=getChar();
    while(isdigit(ch)==0 && ch!='-') ch=getChar();
    if(ch=='-'){
        semn=-1;
        ch=getChar();
    }
    while(isdigit(ch)!=0){
        r=r*10+semn*(ch-'0');
        ch=getChar();
    }
    return r;
}

vector < pair <int,int> > G[50001];
int mindist[50001];
priority_queue <int> q;

int main()
{
    int n,m,i,x,y,c;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    n=getNr();
    m=getNr();
    for(i=1; i<=m; i++)
    {
        x=getNr();
        y=getNr();
        c=getNr();
        G[x].push_back({y,c});
    }
    for(i=2; i<=n; i++)
        mindist[i]=INF;
    q.push(1);
    while(!q.empty())
    {
        int u=q.top();
        q.pop();
        for(auto w : G[u])
            if(mindist[w.nod]>mindist[u]+w.cost)
            {
                mindist[w.nod]=mindist[u]+w.cost;
                q.push(w.nod);
            }
    }
    for(i=2; i<=n; i++)
        printf("%d ",mindist[i]);

    return 0;
}