#include <bits/stdc++.h>

using namespace std;

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

#define INF INT_MAX

const int NMAX = 50001;
vector< pair<int,int> > adjList[NMAX];
int dist[NMAX];
int used[NMAX];

class Prioritize
{
public:
    bool operator ()(pair<int,int>&p1, pair<int,int>&p2)
    {
        return p1.second > p2.second;
    }
};

void DijkstraHeap(int source,int n)
{

    for(int i=0;i<=n;i++)
    {
        dist[i] = INF;
        used[i] = false;
    }

    priority_queue<pair<int,int>, vector<pair<int,int> >,Prioritize> pQueue;

    dist[source] = 0;

    pQueue.push(make_pair(source,dist[source]));

    while(!pQueue.empty())
    {
        pair<int ,int> curr = pQueue.top();

        pQueue.pop();

        int currNode = curr.first;
        int currDistance = curr.second;

        if(used[currNode])
            continue;
        used[currNode] = true;

        for(int i=0;i<adjList[currNode].size();i++)
        {
            if(!used[adjList[currNode][i].first]  && adjList[currNode][i].second + currDistance < dist[adjList[currNode][i].first])
            {
                dist[adjList[currNode][i].first] = adjList[currNode][i].second + currDistance;
                pQueue.push(make_pair(adjList[currNode][i].first, dist[adjList[currNode][i].first]));
            }
        }

    }

}


int main()
{
    int n,m,x,y,cost;
    f>>n>>m;
    for(int i=0;i<m;i++)
    {
        f>>x>>y>>cost;
        adjList[x].push_back(make_pair(y,cost));
    }

    DijkstraHeap(1,n);

    for(int i=2;i<=n;i++)
    {
        if(dist[i]!=INF)
            g<<dist[i]<<" ";
        else
            g<<0<<" ";
    }
    return 0;
}