#include<fstream>
#include<bitset>
#include<iostream>
#include<set>
#include<vector>
#define Nmax 50001
#define INF 0x3f3f3f3f
using namespace std;

void read_data(int &N, vector< pair<int,int> > G[])
{
    int M,x,y,c;

    ifstream f("dijkstra.in");

    f>>N>>M;

    while(M--)
    {
        f>>x>>y>>c;
        G[x].push_back( make_pair(y,c) );
    }
    f.close();
}

void solve(int &N, vector< pair<int,int> > G[], int sol[])
{
    fill(sol + 1, sol + N + 1, INF);

    set< pair<int, int> > heap;

    bitset<Nmax> viz;
    viz.reset();

    heap.insert( make_pair(0, 1) );
    sol[1] = 0;
    viz[1] = 1;

    while(heap.size() != 0)
    {
        auto it = heap.begin();

        int node = it->second;
        int cost = it->first;
        heap.erase(it);

        viz[node] = 0;
        for(auto it2 = G[node].begin(); it2 != G[node].end(); ++it2)
        {
            if(cost + it2->second < sol[it2->first])
            {
                if(viz[node] == 1)
                {
                    auto itFind = heap.find( make_pair(sol[it2->first], it2->first) );

                    if(itFind != heap.end())
                        heap.erase(itFind);
                }

                sol[it2->first] = cost + it2->second;

                heap.insert( make_pair(sol[it2->first], it2->first) );
                viz[node] = 1;
            }
        }
    }
}

void write_data(int &N, int sol[])
{
    ofstream g("dijkstra.out");
    for(int i=2;i<=N;++i)
        g<<sol[i]<<" ";
    g.close();
}
int main()
{

    int N;
    vector< pair<int, int> > G[Nmax];

    read_data(N, G);

    int sol[Nmax];

    solve(N, G, sol);

    write_data(N, sol);

    return 0;
}