#include<fstream>
#include<vector>
#include<set>
#include<utility>
#define NMAX 50010
#define INF 50010000
#define f first
#define s second

using namespace std;

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

vector<pair<int, int> > a[NMAX];

multiset<pair<int, int> > s;

int n, m, d[NMAX], vz[NMAX];

void Citeste()
{
    int x, y, c, i;
    f>>n>>m;
    for (i=1; i<=m; ++i)
    {
        f>>x>>y>>c;
        a[x].push_back(make_pair(y, c));
    }
}

void Solve()
{
    int i, gata=0, nr=0;
    pair<int, int> pr, r;
    multiset<pair<int, int> > :: iterator is;

    for (i=1; i<=n; ++i) d[i]=INF;

    s.insert(make_pair(0, 1)); d[1]=0;

    do
    {
        do
        {
            is=s.begin();
            pr=*is;
            if (vz[pr.s]) s.erase(*is);
        }while (vz[pr.s]==1 && !s.empty());

        if (!s.empty())
        {
            s.erase(is);
            vz[pr.s]=1; ++nr;

            for (i=0; i<a[pr.s].size(); ++i)
            {
                r=a[pr.s][i];
                if (!vz[r.f] && d[r.f]>d[pr.s]+r.s)
                {
                    d[r.f]=d[pr.s]+r.s;
                    s.insert(make_pair(d[r.f], r.f));
                }
            }
        }
        else gata=1;
    }while(!gata && nr<n-1);

    for (i=2; i<=n; ++i)
        if (d[i]==INF) g<<"0 ";
        else g<<d[i]<<" ";

}

int main()
{
    Citeste();
    Solve();
    f.close();
    g.close();
    return 0;
}