#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
struct heapnode
{
    int node,cost;
    bool operator<(const heapnode &other)const
    {
        return cost>other.cost;
    }
};
priority_queue<heapnode>heapmin;
struct elem
{
    int value,lungime;
};
int dist[50005];
vector<elem>g[50005];
void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    //out<<dist[2]<<' ';
    heapnode first;
    first.node=1;
    first.cost=0;
    dist[1]=0;
    heapmin.push(first);
    while(!heapmin.empty())
    {
        int curent=heapmin.top().node;
        int distcurent=heapmin.top().cost;
        heapmin.pop();
        if(dist[curent]<distcurent)
            continue;
        for(int i=0;i<g[curent].size();i++)
        {
            elem vecin=g[curent][i];
            int newdist=distcurent+vecin.lungime;
            if(newdist<dist[vecin.value])
            {
                dist[vecin.value]=newdist;
                heapnode newnode;
                newnode.node=vecin.value;
                newnode.cost=newdist;
                heapmin.push(newnode);

            }
        }

    }
}
int main()
{
    int n,m;
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x;
        elem y;
        in>>x>>y.value>>y.lungime;
        g[x].push_back(y);
    }
    dijkstra();
    for(int i=2;i<=n;i++)
        if(dist[i]!=-1)
            out<<dist[i]<<' ';
        else
            out<<"0"<<' ';
    return 0;
}