#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <climits>

#define YEET 50010

using namespace std;

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

struct Vecin {
    int y, cost;

    bool operator<(const Vecin& other) const {
        if (cost != other.cost)
            return cost < other.cost;
        return y < other.y;
    }
};

set<Vecin> q;
vector<Vecin> edges[YEET];
int d[YEET];

void read (int &n, int &m)
{
    fin>>n>>m;

    int x,y,c;
    for (int i=0;i<m;i++)
    {
        fin>>x>>y>>c;

        edges[x].push_back({y,c});
    }
}

void dijkstra (int n, int nod)
{
    for (int i=1; i<=n; i++)
        if (i!=nod)
            d[i]=INT_MAX;
    d[nod]=0;
    q.insert({nod,0});

    while (!q.empty())
    {
        nod = q.begin()->y;
        q.erase(q.begin());

        for (int i=0; i<edges[nod].size(); i++)
        {
            int vec=edges[nod][i].y;
            int newr = d[nod] + edges[nod][i].cost;

            if (d[vec] > newr)
            {
                if (d[vec]!=INT_MAX)
                    q.erase({vec, d[vec]});
                d[vec] = newr;
                q.insert({vec, d[vec]});
            }
        }
    }
}

int main()
{
    int n,m;
    read(n,m);
    dijkstra(n, 1);

    for (int i=2;i<=n;i++)
    {if (d[i]==INT_MAX)
            d[i]=0;
        fout<<d[i]<<" ";}
    return 0;
}