#include <fstream>
#include <limits>
#include <queue>
using namespace std;

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

typedef pair<int,int> PII;

const int INF = std::numeric_limits<int>::max()/2;



int main()
{
    int n,m; fin>>n>>m;

    vector<vector<PII>> Adj(n+1);

    for(int i=0;i<m;++i){
        int a,b,c; fin>>a>>b>>c;
        Adj[a].push_back(PII(b,c));
    }

    vector<int> dist(n+1,INF);
    priority_queue<PII> pq;
    pq.push(PII(0,1));
    dist[1]=0;


    while(!pq.empty()){
        int v=pq.top().second;
        int w=pq.top().first;
        pq.pop();

        if(w==dist[v]){
            for(auto it=Adj[v].begin(); it!=Adj[v].end();++it){
                int &ng = it->first;
                int &cw = it->second;

                if(dist[ng]>w+cw){
                    dist[ng]=w+cw;
                    pq.push(PII(dist[ng],ng));
                }
            }
        }

    }

    for(int i=2;i<=n;++i){
        fout<< (dist[i]==INF?0:dist[i])<<' ';
    }
    fout<<'\n';

    return 0;
}