#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

using VI = vector<int>;
using PI = pair<int, int>;
using VP = vector<PI>;
using VVP = vector<VP>;

const int Inf = 0x3f3f3f3f;
int n, m;

VVP G;
VI d;


struct Pair
{
    int node;
    int dist;
    bool operator < (const Pair& p) const
    {
        return dist > p.dist;
    }
};

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

    G = VVP(n + 1);

    int x, y, w;

    while(fin >> x >> y >> w)
    {
        G[x].push_back({y, w});
    }
}

void write()
{
    for(int i = 2; i <= n; i++)
    {
        if(d[i] == Inf) fout << 0 << ' ';
        else
            fout << d[i] << ' ';
    }
}

void Dijkstra(int x, VI& d)
{
    d = VI(n + 1, Inf);
    int dx, y, w;

    priority_queue<Pair> Q;
    Q.push({x, 0});
    d[x] = 0;

    while(!Q.empty())
    {
        x = Q.top().node;
        dx = Q.top().dist;

        Q.pop();

        if(dx > d[x]) continue;

        for(auto& p : G[x])
        {
            y = p.first; w = p.second;

            if(d[y] > d[x] + w)
            {
                d[y] = d[x] + w;
                Q.push({y, d[y]});
            }
        }


    }
}


int main()
{
    read();
    Dijkstra(1, d);
    write();

    return 0;
}