#include <fstream>
#include <vector>

using namespace std;

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

pair <int, int> P;

const int NMax=50000;
const int oo=2000000000;
int D[NMax+5], S[NMax+5], N, M, Nod;
vector <pair<int, int> > G[NMax+5];

void Read()
{
    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 Print()
{
    for (int i=2; i<=N; i++)
    {
        if (D[i]==oo)
            fout << 0;
        else fout << D[i] << " ";
    }
}

void Dijkstra()
{
    for (int i=2; i<=N; i++)
        D[i]=oo;
    for (int k=1; k<N; k++)
    {
        int Min=oo;
        for (int i=1; i<=N; i++)
            if (D[i]< Min && S[i]==0)
            {
                Min=D[i];
                Nod=i;
            }
        S[Nod]=1;
        for (int i=0; i<G[Nod].size(); i++)
        {
            int Vecin= G[Nod][i].first, Cost=G[Nod][i].second;
            D[Vecin]=min(D[Vecin], D[Nod]+Cost);
        }

    }
}

int main()
{
    Read();
    Dijkstra();
    Print();
    return 0;
}