//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(50010,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[i]<minn&&vizitat[i]==0)
            {
                minn=d[i]; aux=i;
            }
        }
        vizitat[i]=1; // il marcam ca vizitat
        for(it=v[aux].begin();it!=v[aux].end();it++)
        {
            if(d[it->first]>d[i]+it->second)
            {
                d[it->first]=d[i]+it->second;
            }
        }
    }
    for(i=2;i<=n;++i)
    fout<<d[i]<<" ";



    return 0;
}