#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>

#define BUF_SIZE 1<<17
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}

#define MAXN 50000
#define INF 2000000000

struct Edge{
    int cost;
    int dest;
};
std::vector <Edge> G[1+MAXN];
std::priority_queue <std::pair<int, int> > pq;
int d[1+MAXN];

int main(){
    fi=fopen("dijkstra.in","r");
    fo=fopen("dijkstra.out","w");
    int n=nextnum(), m=nextnum();
    for(int i=0;i<m;i++){
        int a=nextnum(), b=nextnum(), c=nextnum();
        Edge temp;
        temp.cost=c;
        temp.dest=b;
        G[a].push_back(temp);
    }
    for(int i=0;i<=n;i++)
        d[i]=INF;

    pq.push(std::make_pair(0, 1));
    while(!pq.empty()){
        int node=pq.top().second, cost=pq.top().first;
        if(d[node]==INF){
            d[node]=-cost;
            for(int i=0;i<G[node].size();i++)
                if(d[G[node][i].dest]==INF)
                    pq.push(std::make_pair(cost-G[node][i].cost, G[node][i].dest));
        }
        pq.pop();
    }
    for(int i=2;i<=n;i++)
        if(d[i]==INF)
            fprintf(fo,"0 ");
        else
            fprintf(fo,"%d ", d[i]);
    fclose(fi);
    fclose(fo);
    return 0;
}