#include <fstream>
#include <queue>
#include <vector>
using namespace std;

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

const int N = 50001;
const int INF = 1e9;

vector < pair<int, int> > a[N]; //adjacency list
priority_queue < pair<int, int> > pq;
int d[N]; //distances
bool vis[N]; //keeps track of visited vertices

int n, m;

void dijkstra(int s) //source vertex
{
    for (int i = 1; i <= n; ++i)
        d[i] = INF;

    pq.push({0, s});
    d[s] = 0;

    while (!pq.empty())
    {
        int x = pq.top().second; // the currently visited vertex 
        pq.pop();
        
        if (!vis[x])
        {
            vis[x] = true;
            for (auto neighb: a[x]) 
            {
                int y = neighb.first;
                int c = neighb.second;
                if (d[x] + c < d[y])
                {
                    d[y] = d[x] + c;
                    pq.push({-d[y], y});
                }
            }
        }

    }
}

int main()
{
    in >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x, y, c;
        in >> x >> y >> c;
        a[x].push_back({y, c});
    }

    dijkstra(1);

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

        out << d[i] << ' ';
    }
    out.close();
    return 0;
}