#include <fstream>
#include <vector>
#include <queue>
#define Nmax 50009
#define INF 999999999

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

typedef pair<int,int> edge;
#define y first
#define c second

int n,m,x,y,c,S,d[Nmax],parent[Nmax];
vector <edge> G[Nmax];

struct cmp
{
    bool operator()(const int &x, const int &y)
    {
        return d[x] > d[y];
    };
};

priority_queue < int , vector <int> , cmp > pq;

void Dijkstra(int source , int d[Nmax] , int parent[Nmax])
{
    for (int i=1; i<=n; ++i)
        d[i] = parent[i] = INF;
    pq.push(source);
    d[source]=0;
    parent[source]=source;

    while (!pq.empty())
    {
        int node=pq.top();
        pq.pop();
        for (auto x : G[node])
            if (d[x.y]>d[node]+x.c)
            {
                d[x.y]=d[node]+x.c;
                parent[x.y]=node;
                pq.push(x.y);
            }
    }
}

void ReadInput()
{
    f>>n>>m;
    S=1;
    for (int i=1; i<=m; ++i)
    {
        f>>x>>y>>c;
        G[x].push_back(edge(y , c));
    }
}

void Write()
{
    for (int i=1; i<=n; ++i)
        if (d[i]==INF) parent[i] = d[i] = 0;
    for (int i=2; i<=n; ++i) g<<d[i]<<' ';
}

int main()
{
    ReadInput();
    Dijkstra(S , d , parent);
    Write();
    f.close();
    g.close();
    return 0;
}