#include<fstream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

struct coord
{
    int cost,nod;
};

struct coada
{
    int varf,relax;
    bool operator < (const coada& e) const
	{
        return relax > e.relax;
    }
};

vector <coord> v[50005];
int n,m,d[50005];
priority_queue<coada>q;
const int oo=1<<30;

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

inline void Citire()
{
    int i,x;
    coord y;
    fin>>n>>m;
    for (i=1;i<=m;i++)
        {
            fin>>x>>y.nod>>y.cost;
            v[x].push_back(y);
        }
}

inline void DIJKSTRA()
{
    int i,k,len,x;
    coada kl;
    d[1]=0;
    for (i=2;i<=n;i++)
        d[i]=oo;
    k=1;x=1;
    kl.varf=1;
    kl.relax=0;
    q.push(kl);
    while (!q.empty())
        {
            x=q.top().varf;
            q.pop();
            len=v[x].size();
            for (i=0;i<len;i++)
                if (d[v[x][i].nod]>d[x]+v[x][i].cost)
                    {
                        d[v[x][i].nod]=d[x]+v[x][i].cost;
                        kl.varf=v[x][i].nod;
                        kl.relax=d[v[x][i].nod];
                        q.push(kl);
                    }
        }
}

inline void Afisare()
{
    int i;
    for (i=2;i<=n;i++)
        if (d[i])
            fout<<d[i]<<" ";
        else fout<<"0 ";
    fout<<"\n";
}

int main()
{
    Citire();
    DIJKSTRA();
    Afisare();
    return 0;
}