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

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct heap_node
{
    int nod,dist;
    bool operator<(const heap_node &other) const
    {
        return dist>other.dist;
    }
};
struct edge
{
    int nod;
    int dist;
};
priority_queue<heap_node> pq;
vector<vector<edge>>g;
vector<int>dist;
const int NMAX=1000000;
void bfs()
{
    heap_node start_node;
    start_node.nod=1;
    start_node.dist=0;
    pq.push(start_node);
    while(!pq.empty())
    {
        int frn=pq.top().nod;
        pq.pop();

        for(int i=0; i<g[frn].size(); i++)
        {
            edge vecin = g[frn][i];
            if(vecin.dist+dist[frn]<dist[vecin.nod])
            {
                dist[vecin.nod]=vecin.dist+dist[frn];
                heap_node urm;
                urm.dist=dist[vecin.nod];
                urm.nod=vecin.nod;
                pq.push(urm);
            }
        }
    }
}

int main()
{
    int n,m,a,b,c;
    fin>>n>>m;
    g.resize(n+1);
    dist.resize(n+1);
    for(int i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        edge edg;
        edg.dist = c;
        edg.nod = b;
        g[a].push_back(edg);
    }
    for(int i=1; i<=n; i++)
    {
        dist[i]=NMAX;
    }
    dist[1]=0;
    bfs();
    for(int i=2;i<=n;i++)
    {
        if (dist[i] == NMAX) {
            fout << 0 << ' ';
        } else {
            fout<<dist[i]<<" ";
        }
    }
}