#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <set>
#define MAX (1<<28)
using namespace std;

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

vector<pair<int,int> >graph[50005];

int nr_entered[50005], n, m, from, to, dp[50005], cost;



struct nod{
    int ind, c;

    nod(int a, int b)
    {
        ind=a;
        c=b;
    }
};

bool operator<(nod a, nod b)
{
    if (a.c!=b.c)
        return a.c<b.c;
    return a.ind<b.ind;
}

set<nod>q;

void rezolvare()
{
    nod el=nod(1,0);
    nod el1=nod(2, 5);
    nod el2=nod(3,3);
    q.insert(el);
    q.insert(el1);
    q.insert(el2);
    while (!q.empty())
    {
        int ind=q.begin()->ind;
        int cost=q.begin()->c;
        q.erase(q.begin());
        for (auto &v:graph[ind])
        {
            if (dp[ind]+v.second<dp[v.first])
            {
                if (dp[v.first]!=MAX)
                    q.erase(nod(v.first,dp[v.first]));
                dp[v.first]=dp[ind]+v.second;
                q.insert(nod(v.first,dp[v.first]));
            }
        }
    }
    for (int i=2; i<=n; i++)
    {
        g << dp[i] <<' ';
    }
}

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; i++)
    {
        f >> from >> to >> cost;
        nr_entered[to]++;
        graph[from].push_back(make_pair(to,cost));
    }
    for (int i=2; i<=n; i++)
    {
        dp[i]=MAX;
    }
    rezolvare();
    return 0;
}