#include <cstdio>
#include <vector>
using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define rint register int


const int NOD = 50100;
const int INF = 1<<30;

typedef pair <int,int> P;
vector <P> gr[NOD];

int n,d[NOD],pred[NOD],heap[NOD],poz[NOD],nh;
void dijkstra(int st);
void upheap(int nod);
void sterge(int nod);
void downheap(int nod);
void schimba(int poza, int pozb);
inline void init(int x);
int main()
{
    int m;
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d%d",&n,&m);
    while(m--){
        int x,y,cost;
        scanf("%d%d%d",&x,&y,&cost);
        gr[x].pb(mp(y,cost));
    }
    dijkstra(1);
    for(rint i=2;i<=n;i++)printf("%d ",(d[i]==INF)?0:d[i]);
    return 0;
}
void dijkstra(int st){
    init(st);
    nh=n;
    while(nh>0){
        int nod=heap[1];
        if(d[nod]==INF) break;
        for(rint i=0;i<(int)gr[nod].size();i++){
            int y = gr[nod][i].f;
            int w = gr[nod][i].s;
            if(d[nod]+w<d[y]){
                d[y] = d[nod]+w;
                pred[y] = nod;
                upheap(poz[y]);
            }
        }
        sterge(1);
    }
}
inline void upheap(int nod){
    if(nod==1) return;
    int tata = nod/2;
    if(d[heap[tata]]>d[heap[nod]]){
        schimba(tata, nod);
        upheap(tata);
    }
}
inline void schimba(int poza, int pozb){
    swap(heap[poza], heap[pozb]);
    swap(poz[heap[poza]], poz[heap[pozb]]);
}
inline void sterge(int nod){
    schimba(nod, nh);
    nh--;
    downheap(nod);
}
inline void downheap(int nod){
    if(nod*2>nh) return;
    int fiumin = nod*2;
    if(nod*2+1<=nh and d[heap[fiumin]]>d[heap[2*nod+1]])
        fiumin = 2*nod+1;
    if(d[heap[nod]]>d[heap[fiumin]]){
        schimba(nod, fiumin);
        downheap(fiumin);
    }
}
inline void init(int x){
    for(rint i=1;i<=n;d[i]=INF,pred[i]=0,heap[i]=poz[i]=i,++i);
    heap[1]=x;heap[x]=1;
    poz[1]=x;poz[x]=1;
    d[x]=0;
}