#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>


#define pp pair<int,int>

using namespace std;

const int MaxN = 50001;
const int INF = 0x3f3f3f3f;

vector < pair < int , int > > G[MaxN];
int d[MaxN],n,m;

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

    int x,y,c;

    f >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        f >> x >> y >> c;
        G[x].push_back(make_pair(y,c));
    }

    int source = 1;

    priority_queue < int, vector < int > ,greater< int > > pq;

    memset(d,INF,sizeof(d));
    d[source] = 0;

    pq.push(source);

    while(!pq.empty())
    {
        int node = pq.top();
        pq.pop();

        for(vector<pp>::iterator i = G[node].begin(); i != G[node].end(); ++i)
        {
            if(d[i -> first] > d[node] + i -> second)
            {
                d[i -> first] = d[node] + i -> second;
                pq.push(i -> first);
            }
        }
    }

   for(int i = 2; i <= n; ++i)
        g << (d[i] < INF ? d[i] : 0) << " ";

    return 0;
}