///Dijkstra cu HEAP (implementat in STL)

///Time Complexity : O ( M * logN )

/// (c) Cosmin Rusu
#include <fstream>
#include <vector>
#include <queue>

#define pb push_back
#define mp make_pair
///TODO - HONEST
using namespace std;

const int N = 50005;
const int oo = ((1<<30));

vector < pair<int, int> > G[N];
vector < int > d(N, oo);
priority_queue< pair<int, int> , vector< pair<int, int> > , greater< pair<int, int> > > heap;
///kind of a min-HEAP
int n, m;

void read_info();
void dijkstra();
void write_data();

int main()
{
    read_info();
    dijkstra();
    write_data();
    return 0;
}

void read_info()
{
    ifstream f("dijkstra.in");
    f >> n >> m;
    for(int i = 1 ; i <= m ; ++ i)
    {
        int x, y, z;
        f >> x >> y >> z;
        G[x].pb(mp(y, z));
    }
    f.close();
}
void dijkstra()
{
    for( heap.push(mp(0, 1)), d[1] = 0 ; !heap.empty(); )
    {
        int nod = heap.top().second;
         heap.pop ();
        for( vector< pair<int, int> > :: iterator it = G[nod].begin(); it != G[nod].end(); ++ it)
        {
            int newnode = it->first;
            int cost = it->second;
            if( d[newnode] > d[nod] + cost)
            {
                d[newnode] = d[nod] + cost;
                heap.push(mp(d[newnode] , newnode));
            }
        }
    }
}
void write_data()
{
    ofstream g("dijkstra.out");
    for(int i = 2 ; i <= n ; ++ i)
        if(d[i] == oo)
            g << "0 ";
        else g << d[i] << " ";
    g.close();
}