#include <fstream>
#include <vector>
#include <queue>
#define INF 1000000000

using namespace std;

struct cmp{
    bool operator()(pair <int,int> &p1,pair <int,int> &p2){
        return p1.second>p2.second;
    }
};
priority_queue <pair <int,int>,vector <pair <int,int> >,cmp> Q;
vector <pair <int,int> > G[50005];
int n,m,dist[50005];
void read();
void djikstra(int);
void write();
int main(){
    read();
    djikstra(1);
    write();
    return 0;
}

void read(){
    freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        G[x].push_back(make_pair(y,c));
        //G[y].push_back(make_pair(x,c));
    }
}

void djikstra(int x){
    for (int i=1;i<=n;i++){
        dist[i]=INF;
    }
    dist[x]=0;
    Q.push(make_pair(x,0));
    while (!Q.empty()){
        int x=Q.top().first;
        Q.pop();
        for (int i=0;i<G[x].size();i++){
            int nod=G[x][i].first;
            int cost=G[x][i].second;
            if (dist[nod]>dist[x]+cost){
                dist[nod]=dist[x]+cost;
                Q.push(make_pair(nod,dist[x]+cost));
            }
        }
    }
}

void write(){
    freopen("dijkstra.out","w",stdout);
    for (int i=2;i<=n;i++){
        dist[i]!=INF?printf("%d ",dist[i]):printf("0 ");
    }
}