#include<fstream>
#include<queue>
#include<vector>
#define nmax 50008
using namespace std;

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

int N, M, d[nmax];
bool o[nmax];
struct Nod {
int x, cost;
    Nod(int _x, int _cost)
    {
        x = _x;
        cost = _cost;

    }
    Nod()
    {
        x = 0 ;cost = 0;

    }
    bool operator <(const Nod f) const
    {
        return cost > f.cost;
    }

};
vector <Nod> G[nmax];
void read()
{
    fin >> N>> M;

    for(int i = 1; i <= M; i++)
    {
        int x,y, c;
        fin >> x>>y >>c;
        G[x].push_back(Nod(y,c));

    }
}
void Dijkstra()
{
    for(int i = 1; i <= N; i++)
        d[i] = 10000000;
    d[1] = 0 ;
    priority_queue <Nod> H;
    H.push(Nod(1,0));
    while(! H.empty())
    {
        int x = H.top().x;
        H.pop();

        for(vector <Nod>:: iterator it  = G[x].begin(); it != G[x].end(); it++ )
        {
            int y = it -> x;
            int c = it -> cost + d[x];
            if(d[y] > c)
            {
                d[y] = c;
                H.push(Nod(y,c));
            }
        }
    }
    for(int i = 2; i <= N; i++)
    {
        if(d[i] == 10000000)
            fout << 0;
        else
            fout << d[i];
        fout << " ";
    }

}
int main()
{
    read();
    Dijkstra();
    fin.close();

    return 0;
}