#include <iostream>
#include <fstream>
#include <limits.h>
#include <vector>
#include <queue>
using namespace std;

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

int i,j, n,m, a,b,cost, current_dist;
long INFINIT = LONG_MAX;
typedef pair<int, int> nod;
vector<nod>G[50001];

int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)  {
        f>>a>>b>>cost;
        G[a].push_back(nod(b, cost));
    }
    int plecare = 1;
    int dist[n+1];
    for (i=1;i<=n;i++)
        dist[i] = INFINIT;

    dist[plecare] = 0;

    priority_queue< nod, vector<nod>, greater<nod> > pq;//heap
    pq.push(nod(0, plecare));

    while ( !pq.empty() )   {
        nod top = pq.top();
        pq.pop();
        int d = top.first;
        int nod_curent = top.second;

        int heapSize;
        for (i=0; i<(int)G[nod_curent].size();++i)   {
            b = G[nod_curent][i].first;
            current_dist = G[nod_curent][i].second;

            if (dist[nod_curent] + current_dist < dist[b])  {
                dist[b] = dist[nod_curent] + current_dist;
                pq.push(nod(dist[b], b));
            }
        }
    }

for (i=2;i<=n;i++)  {
    if (dist[i]==INFINIT)
        dist[i]=0;
    g<<dist[i]<<" ";
}
    /*
    priority_queue<pp, vector<pp > , Prioritize > H;//heap
    f>>n>>m;
    vector<pp> G[n+1];
    for (i=0;i<m;i++)  {
        f>>a>>b>>cost;
        G[a].push_back(pp(b,cost));
        G[b].push_back(pp(a,cost));
//        cost[a][b] = c;
    }
    int plecare = 1;
    int dist[n+1];

    for (i=1;i<=n;i++)  {
        dist[i] = INFINIT;
    }
    dist[plecare] = 0;
    H.push(pp(plecare, dist[plecare]));
    while (!H.empty())  {
        a = H.top().first;
        H.pop();
        int heapSize = G[a].size();//cout<<heapSize;
        for (i=0;i<heapSize;i++)    {
            a = G[a][i].first;
            b = G[a][i].second;
           // cout<<"\n"<<a<<" "<<b<<" "<<cost;
            if (dist[b] > dist[a] + cost) {
                dist[b] = dist[a] + cost;
                H.push(pp(b,dist[b]));
            }
        }
    }
    cout<<"----------------------------"<<endl;
    for (i=1;i<=n;i++)
        cout<<i<<" "<<dist[i];
*/
    //dijkstra(1);
    //   g<<d[i]<<"\t";
    return 0;
}