#include <iostream>
#include <fstream>
#include <vector>
#define MAX 10000000
using namespace std;
int n,m,i,d[50001],nod,viz[50001],x,y,c,ok,maxi,k,num,j;
struct ev{int l,c;};
vector <int> a[250001],co[250001];
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(i=1;i<=n;i++)d[i]=MAX;
    nod=1;
    viz[nod]=1;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x].push_back(y);
        co[x].push_back(c);
        if(x==nod)d[y]=c;
    }
    /*for(i=1;i<=n;i++)
    {
        for(j=0;j<a[i].size();j++)cout<<a[i][j]<<'-'<<co[i][j]<<' ';
        cout<<'\n';
    }*/
    ok=1;
    while(ok)
    {
        ok=0;
        maxi=MAX;
        for(i=1;i<=n;i++)if(viz[i]==0&&d[i]<maxi)
        {
            ok=1;
            maxi=d[i];
            k=i;
        }
        if(ok==1)
        {
            viz[k]=1;
            for(i=0;i<a[k].size();i++)
            {
                if(d[k]+co[k][i]<d[a[k][i]])d[a[k][i]]=d[k]+co[k][i];
            }
        }

    }
    for(i=1;i<=n;i++)if(i!=nod)
    {
        if(d[i]!=MAX)g<<d[i]<<' ';
        else g<<0<<' ';
    }
    f.close();
    g.close();
}