//dijkstra O(n*n) fara vector de tati - sursa infoarena 40 pct made by andreimdv
#include<fstream>
#include<vector>
#include<list>
using namespace std;

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

vector<list<pair<int,int> > >v(50010);
list<pair<int,int> > :: iterator it;
int n,m,i,minn,a,b,c,j,aux,vizitat[50010];
vector<int> d(10,1<<30);

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
    }
    d[1]=0;
    for(i=1;i<n;++i)
    {
        minn=1<<30;
        for(j=1;j<=n;++j) // cautam minimul nevizitat
        {
            if(d[j]<minn&&vizitat[j]==0)
            {
                minn=d[j]; aux=j;
            }
        }
        vizitat[aux]=1; // il marcam ca vizitat
        for(it=v[aux].begin();it!=v[aux].end();it++)
        {
            if(d[(*it).first]>d[aux]+(*it).second)
            {
                d[(*it).first]=d[aux]+(*it).second;
            }
        }
    }
    for(i=2;i<=n;++i)
    if(d[i]==1<<30)
    fout<<"0 ";
    else
    fout<<d[i]<<" ";



    return 0;
}