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

typedef std::pair<int, int> pair;

std::ifstream in("dijkstra.in");
std::ofstream out("dijkstra.out");

const int N=50000;
const int M=250000;
const int INF=2000000000;

struct muchie
{
    int from;
    int to;
    int cost;
};

int dist[N+1];
std::vector<int> v[N+1];
muchie edge[M+1];

bool visited[N+1];

bool compare(std::pair<int, int> a, std::pair<int, int> b)
{
    if(a.first!=b.first)
        return a.first>b.first;
    else
        return a.second>b.second;
}

std::priority_queue< std::pair<int, int> , std::vector<std::pair<int, int>> , decltype(&compare) > q(&compare);

//std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;

void Dijkstra()
{
    q.push({0, 1});

    while(!q.empty())
    {
        int top=q.top().second;
        int curr=q.top().first;

        if(!visited[top])
        {
            visited[top]=1;
            dist[top]=curr;

            for(int side : v[top])
            {
                if(!visited[edge[side].to])
                {
                    if(dist[top]+edge[side].cost<dist[edge[side].to])
                    {
                        q.push({dist[top]+edge[side].cost, edge[side].to});
                    }
                }
            }
        }

        q.pop();
    }
}

int n, m;

int main()
{
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>edge[i].from>>edge[i].to>>edge[i].cost;
        v[edge[i].from].push_back(i);
    }

    for(int i=1; i<=n; i++)
    {
        dist[i]=INF;
    }
    Dijkstra();

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