#include <bits/stdc++.h>

using namespace std;

const int N=50005, Inf=2000000000;
typedef pair<int,int> Pair;
vector <Pair> G[N];
int dist[N];
priority_queue <Pair, vector<Pair>, greater<Pair> > pq;

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    int n,m,a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        G[a].push_back({b,c});
    }
    for(int i=1;i<=n;i++) dist[i]=Inf;

    dist[1]=0;
    pq.push({0,1});

    while(!pq.empty()){
        int d=pq.top().first;
        int x=pq.top().second;
        pq.pop();
        if(d>dist[x]) continue;

        for(int i=0;i<G[x].size();i++){
            int y=G[x][i].first;
            int d=G[x][i].second;

            if(dist[x]+d<dist[y]){
                dist[y]=dist[x]+d;
                pq.push({dist[y],y});
            }
        }
    }
    for(int i=2;i<=n;i++) printf("%d ",dist[i]);

    return 0;
}