#include<fstream>
#include<set>
#include<vector>
#include<utility>
#define NMAX 50010
#define INF 250000010
#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;
    f>>n>>m;
    while(m--)
    {
        f>>x>>y>>c;
        a[x].push_back(make_pair(c, y));
    }
}

void Solve()
{
    int i, nr=1;
    pair<int, int> pr, r;

    for (i=2; i<=n; ++i) D[i]=INF;

    s.insert(make_pair(0, 1));
    while (nr<=n && !s.empty())
    {
        pr=*s.begin(); s.erase(s.begin());

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

            for (i=0; i<a[pr.s].size(); ++i)
            {
                r=a[pr.s][i];

                if (!vz[r.s] && r.f+pr.f<D[r.s])
                {
                    D[r.s]=r.f+pr.f;
                    s.insert(make_pair(D[r.s], r.s));
                }
            }
        }
    }
}

void Scrie()
{
    int i;

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

int main()
{
    Citeste();

    Solve();

    Scrie();

    f.close();
    g.close();
    return 0;
}