#include <bits/stdc++.h>

using namespace std;

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

int oo = 100000;
int N, M;
int D[50001];
bool verifi[50001];

vector< pair <int, int> > G[50001];

struct compara
{
    bool operator()(int x, int y)
    {
        return D[x] > D[y];
    }
};
priority_queue< int, vector<int>, compara > Codita;

void citeste()
{
    fin >> N >> M;
    for(int i=1; i<=M; i++)
    {
        int x, y, c;
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y, c));
    }
}

void Dijikstra(int nStart)
{
    for(int i=1; i<=N; i++)
        D[i] = oo;
    D[nStart] = 0;

    Codita.push(nStart);
    verifi[nStart] = true;

    while(!Codita.empty())
    {
        int nCurent = Codita.top();
        Codita.pop();

        verifi[nCurent] = 0;
        for(size_t i = 0; i < G[nCurent].size(); i++)
        {
            int vecin = G[nCurent][i].first;
            int lungime = G[nCurent][i].second;
            if(D[nCurent] + lungime < D[vecin])
            {
                D[vecin] = D[nCurent] + lungime;

                if(!verifi[vecin])
                {
                    Codita.push(vecin);
                    verifi[vecin] = true;
                }
            }
        }
    }

}

void afiseaza()
{
    for(int i=2; i<=N; i++)
    {
        if(D[i] != oo)
            fout<<D[i]<<" ";
        else
            fout<<"0 ";
    }
}
int main()
{
//    ifstream fin("dijkstra.in");
//    ofstream fout("dijkstra.out");

    citeste();
    Dijikstra(1);
    afiseaza();



    return 0;
}