#include <iostream>
#include <queue>
#include <vector>
#include <fstream>

using namespace std;

priority_queue <pair<int,int>,vector<pair<int,int>>,greater <pair<int,int>>> q;
int vis[100005];
int dist[100005];
vector <pair<int,int>> mu[100005];
int n,m,s,a,b,c;

 ifstream in("dijkstra.in");
 ofstream out("dijkstra.out");

void dijkstra(int start){
    q.push({0,start});
    dist[start]=0;
    while(!q.empty()){
        pair<int,int> x=q.top();
        if(vis[x.second]==1){
                q.pop();
        }
        else
        {
            vis[x.second]=1;
            for(int i=0;i<mu[x.second].size();i++)
                if(dist[mu[x.second][i].first]>x.first+mu[x.second][i].second)
                    {
                        q.push({x.first+mu[x.second][i].second,mu[x.second][i].first});
                        dist[mu[x.second][i].first]=x.first+mu[x.second][i].second;
                    }
                q.pop();
        }
    }
}

int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>a>>b>>c;
        mu[a].push_back({b,c});
    }
    for(int i=1;i<=n;i++)
        dist[i]=INT_MAX;
    dijkstra(1);
    for(int i=2;i<=n;i++)
        out<<dist[i]<<" ";

    return 0;
}