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

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
struct elem
{
    int node;
    int cost;
};
struct heapnode
{
    int node;
    long long cost;
    bool operator < (const heapnode & other) const
    {
        return cost > other.cost;
    }
};
const int nmax = 50001;
long long dist[nmax];//!!!
vector<elem>g[nmax];
priority_queue<heapnode>heapmin;//!!!

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    heapnode start;
    start.node = 1;
    start.cost = 0;
    dist[start.node] = 0;
    heapmin.push(start);
    while(!heapmin.empty())
    {
        int curent = heapmin.top().node;
        int costcurr = heapmin.top().cost;
        heapmin.pop();

        if(dist[curent] < costcurr)///daca distanta obntinuta pana acum a fost mai buna decat costul gasit acum doar pt un node, sarim
            continue;

        for(int i = 0; i < g[curent].size(); i++)
        {
            int vecin = g[curent][i].node;
            int cost_vecin = g[curent][i].cost;
            if(costcurr + cost_vecin < dist[vecin])
            {
                heapnode newnode;
                newnode.node = vecin;
                newnode.cost = costcurr + cost_vecin;
                dist[vecin] = costcurr + cost_vecin;

                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.node>>y.cost;
        g[x].push_back(y);
    }

    dijkstra();

    for(int i = 2; i <= n; i++)
    {
        if(dist[i] != 0x3f3f3f3f3f3f3f3f)
            out<<dist[i]<<' ';
        else
            out<<0<<' ';
    }
    return 0;
}