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

using namespace std;
struct node_hp
{
    int node,total;
    bool operator <(const node_hp& other)const
    {
        return total>other.total;
    }
};
priority_queue<node_hp>heap;
struct muchie
{
    int node,cost;
};
const int N=50001;
vector<muchie>graf[N];
long long cost_total[N];

void Dijkstra(int node)
{
    node_hp val;
    val.node=node;
    val.total=0;
    heap.push(val);
    while(!heap.empty())
    {
        node_hp node_cur=heap.top();
        heap.pop();
        for(int i=0;i<graf[node_cur.node].size();i++)
        {
             muchie urm_muchie=graf[node_cur.node][i];
             if(cost_total[node_cur.node]+urm_muchie.cost<cost_total[urm_muchie.node])
             {
                 cost_total[urm_muchie.node]=cost_total[node_cur.node]+urm_muchie.cost;
                 node_hp urmbun;
                 urmbun.node=urm_muchie.node;
                 urmbun.total=cost_total[urm_muchie.node];
                 heap.push(urmbun);
             }
        }
    }
}

int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    int n,m;
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        muchie m;
        in>>x>>m.node>>m.cost;
        graf[x].push_back(m);
    }
    for(int i=2;i<=n;i++)
        cost_total[i]=5000000010;
    Dijkstra(1);
    for(int i=2;i<=n;i++)
    {
        if(cost_total[i]==5000000010)
            out<<0<<' ';
        else
            out<<cost_total[i]<<' ';
    }
    in.close();
    out.close();
    return 0;
}