#include <fstream>
#include <vector>
#include <algorithm>
#define MAX_SIZE 50001

using namespace std;


vector <int> graf[MAX_SIZE];
vector <int> w[MAX_SIZE];
pair <int , int> tree[3 * MAX_SIZE];
bool sel[MAX_SIZE];
int cost[MAX_SIZE];
int N , M;
const int infinit = 1 << 30;


void build_tree(int nod , int left , int right)
{
    if (left == right)
    {
        tree[nod].first = infinit;
        tree[nod].second = left;
        return;
    }
    else
    {
        int middle = (left + right) >> 1;
        int left_son = nod << 1;
        int right_son = left_son + 1;
        build_tree(left_son , left , middle);
        build_tree(right_son, middle+1 , right);
        if ( tree[left_son].first > tree[right_son].first)
        {
            tree[nod] = tree[right_son];
        }
        else
        {
            tree[nod] = tree[left_son];
        }
    }

}

void update_tree(int nod , int left , int right ,int A , int value)
{
    if (left == right)
    {
        tree[nod].first = value;
        tree[nod].second = A;
        return;
    }
    else
    {
        int middle  = (left + right) >> 1;
        int left_son = nod << 1;
        int right_son = left_son + 1;
        if (A <= middle)
        {
            update_tree(left_son , left , middle , A , value);
        }
        if ( middle < A)
        {
            update_tree(right_son , middle + 1 , right , A , value);
        }
        if ( tree[left_son].first > tree[right_son].first)
        {
            tree[nod] = tree[right_son];
        }
        else
        {
            tree[nod] = tree[left_son];
        }
    }
}

void dijkstra(int nod)
{
    cost[nod] = 0;
    update_tree(1,1,N,nod,0);
    for (int k =0;k<N;k++)
    {
        nod = tree[1].second;
        sel[nod] = true;
        update_tree(1,1,N,nod,infinit);

        for (int i =0;i<graf[nod].size();i++)
        {
            int x = graf[nod][i];

            if (cost[x] > w[nod][i] + cost[nod] && sel[x] == false)
            {
                cost[x] = w[nod][i] + cost[nod];
                update_tree(1,1,N,x,cost[x]);
            }
        }
    }
}

void read_data()
{
    ifstream input("dijkstra.in");
    input >> N >> M;
    for (int i = 0;i<M;i++)
    {
        int x , y , c;
        input >> x >> y >> c;
        graf[x].push_back(y);
        w[x].push_back(c);

    }
    input.close();
}

void print_data()
{
    ofstream output("dijkstra.out");
    for (int i = 2;i<=N;i++)
    {
        if (cost[i] != infinit)
        {
            output << cost[i] << " ";
        }
        else
        {
            output << 0 << " ";
        }
    }
    output.close();
}



int main()
{
    read_data();
    fill(cost+1,cost+N+1,infinit);
    build_tree(1,1,N);
    dijkstra(1);
    print_data();
    return 0;
}