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

typedef pair<int, int> PII;

const int INF = numeric_limits<int>::max()>>1;


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

    int n,m;
    fin>>n>>m;

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

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

    while(!q.empty()){
        int v=q.top().second;
        int d=q.top().first;
        q.pop();

        if(d==dist[v])
            for(auto it=Adj[v].begin();it!=Adj[v].end();++it)
                if(dist[it->first]>d+it->second){
                    dist[it->first]=d+it->second;
                    q.push(PII(dist[it->first],it->first));
                }

    }


    for(int i=2;i<=n;++i)
        if(dist[i]==INF) fout<<"0 ";
        else fout<<dist[i]<<' ';
    fout<<'\n';
}