#include <fstream>
#include <vector>
#include <cstring>
#include <set>
#define NMAX 50000 + 1
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int dist[NMAX], n, m;
const int INF = 0x3f3f3f3f;
vector< pair<int, int> > arce[NMAX];
set< pair<int, int> > h;

void Read()
{
    fin >> n >> m;

    int x, y, z;
    for(int i = 1; i <= m; ++ i)
    {
        fin >> x >> y >> z;
        arce[x].push_back(make_pair(y, z));
    }
}

void Write()
{
    for(int i = 2; i <= n; ++ i)
    {
        if(dist[i] == INF)
            dist[i] = 0;

        fout << dist[i] << ' ';
    }

    fout << '\n';
}


int main()
{
    Read();

    memset(dist, INF, sizeof(dist));

    dist[1] = 0;
    h.insert(make_pair(0, 1));

    while(!h.empty())
    {
        int node = h.begin()->second;
        int d = h.begin()->first;
        h.erase(h.begin());

        for(vector<pair<int,int>>::iterator it = arce[node].begin(); it != arce[node].end(); ++ it)
        {
            int to = it->first;
            int cost = it->second;

            if(dist[to] > dist[node] + cost)
            {
                if(dist[to] != INF)
                    h.erase(h.find(make_pair(dist[to], to)));

                dist[to] = dist[node] + cost;
                h.insert(make_pair(dist[to], to));
            }
        }
    }

    Write();

    return 0;
}