#include <fstream>
#include <vector>
#include <utility>

using namespace std;

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

vector <pair <int , int> > v[50001];

int i,n,m,x,y,c,p,dmin[50001],oo=16000,pre[50001];
bool viz[50001];

void dijkstra()
{
    int mini,ok=1,j;
    for(j=1;j<n;j++)
    {
       mini=oo;
       for(i=1;i<=n;i++)
        if(dmin[i]<mini && !viz[i])
        {
            mini=dmin[i];
            p=i;
        }
        viz[p]=1;
        for(i=0;i<v[p].size();i++)
            if(!viz[v[p][i].first] && dmin[v[p][i].first]>mini+v[p][i].second)
            dmin[v[p][i].first]=mini+v[p][i].second;

    }
}

int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        dmin[i]=oo;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        if(x==1)
        dmin[y]=c;
    }
    viz[1]=true;
    dmin[1]=oo;
    dijkstra();
    for(i=2;i<=n;i++)
        g<<((dmin[i]==oo)?0:dmin[i])<<" ";
        return 0;
}