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

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

const int N = 50001;
const int M = 250001;
const int inf = 5*1e7;

struct cost {
    cost(int v, int c) { this->v = v; this->c = c; }
    cost(const cost &ob) { v = ob.v; c = ob.c; }
    int v; int c;
};

vector<cost> vecini[N];
int dist[N];

struct minim {
    bool operator() (const int &a, const int &b) const
    { return dist[a] > dist[b]; }
};

void dijkstra()
{
    priority_queue<int, vector<int>, minim> Q;
    Q.push(1); // Sursa cu dist[1] == 0
    while (!Q.empty())
    {
        int curent = Q.top(); Q.pop();
        for (int i = 0; i < vecini[curent].size(); i++)
        {
            cost vec(vecini[curent][i]);
            int alt = dist[curent] + vec.c;
            if (alt < dist[vec.v])
            {
                dist[vec.v] = alt;
                Q.push(vec.v);
            }
        }
    }
}

int main()
{
    int n, m, x, y, c;
    in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        in >> x >> y >> c;
        vecini[x].push_back(cost(y ,c));
    }
    // dist[1] ramane 0; 1 este nodul de inceput
    for (int i = 2; i <= n; i++) dist[i] = inf;
    dijkstra();
    for (int i = 2; i <= n; i++)
        out << dist[i] << ' ';
    return 0;
}