#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

vector< pair <int,int> > a[50004];

int i,j,vec,c,n,m,x,y,d[50005];

set< pair <int,int> >s;

int main()
{
    fin >> n >> m;
    for (i=1;i<=n;i++) d[i]=2000000005;
    for (i=1;i<=m;i++)
    {
        fin >> x >> y >> c;
        a[x].push_back({y,c});
    }
    d[1]=0;
    do
        {
        if (s.empty()==1) i=1;
        else
        {
            i=s.begin()->second;
            s.erase(s.begin());
        }
        for (j=0;j<a[i].size();j++)
        {
            vec=a[i][j].first;
            c=a[i][j].second;
            if (d[i]+c<d[vec])
            {
                s.erase({d[vec],vec});
                d[vec]=d[i]+c;
                s.insert({d[vec],vec});

            }
        }
    } while (s.empty()==0);
    for (i=2;i<=n;i++) if(d[i]!=2000000005) fout << d[i] << " ";
    else fout << 0 << " ";

    return 0;
}