#include<fstream>
#include<vector>
#include<set>
#define NMAX 50010
using namespace std;
fstream fin("dijkstra.in",ios::in),fout("dijkstra.out",ios::out);
vector <pair<int,int> > v[NMAX];
multiset <int> :: iterator it;
vector <int> :: iterator vt;
vector <int> how[NMAX];
multiset <int> heap;
int n,m,d[NMAX];
int search()
{
    if(heap.empty()==1) return -1;
    it=heap.begin();
    return *it;
}
void dijkstra()
{
    int a,b,i,j,cmin,pmin;
    for(i=1;i<=n+n;i++)
    {
        cmin=search();
        if(cmin>-1)
        {
            vt=how[cmin].begin();
            pmin=*vt;//cui apartine valoarea cmin
            how[cmin].erase(vt);//il sterg din lista pe pmin
            if(0<pmin && pmin<=NMAX)
            {
                for(j=0;j<v[pmin].size();j++)
                {
                    a=v[pmin][j].first;
                    b=v[pmin][j].second;
                    if(d[a]>cmin+b || d[a]==0)
                    {
                        d[a]=cmin+b;
                        how[d[a]].push_back(a);
                        heap.insert(d[a]);
                    }
                }
                heap.erase(heap.begin());
            }
        }
    }
}
int main()
{
    int i,j,a,b,c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
    }
    d[1]=0;
    how[0].push_back(1);
    heap.insert(0);
    dijkstra();
    for(i=2;i<=n;i++)
    {
        fout<<d[i]<<" ";
    }
}