#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50005
#define INF 1000000002

using namespace std;

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

int n,m,p=1;
struct varf{
    int vf,cost;
};
vector<pair<int,int> > G[NMAX];
int cmin[NMAX],pre[NMAX];
bool uz[NMAX];

class ComparVf
{
    public:
        bool operator() (const int& x, const int& y)
        { return cmin[x]>cmin[y]; }
};
priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > H;

void citire();
void afisare();
void Dijkstra();

int main()
{
    citire();

    Dijkstra();

    afisare();

    return 0;
}

void citire()
{
    int i,x,y,c;
    fin>>n>>m;
    pair<int, int> vf;
    for(i=0; i<m; i++){
        fin>>x>>y>>c;
        vf.first=y;
        vf.second=c;
        G[x].push_back(vf);
    }
}

void afisare()
{
    int i;
    for(i=2; i<=n; i++)
        if(cmin[i]==INF) fout<<0<<' ';
            else fout<<cmin[i]<<' ';
}

void Dijkstra()
{
    int i,vfmin,x,c;
    pair<int, int> pp;
    pp.first=0; pp.second=p;

    H.push(pp);


    for(i=1; i<=n; i++)
        cmin[i]=INF;
    cmin[p]=0;

    while(!H.empty()){
        vfmin=H.top().second; H.pop();

        if(cmin[vfmin]==INF) break;

        if(!uz[vfmin])
            for(i=0; i<G[vfmin].size(); i++){
                x=G[vfmin][i].first;
                c=G[vfmin][i].second;

                if(cmin[x]>cmin[vfmin]+c)
                {   cmin[x]=cmin[vfmin]+c;
                    pp.first=cmin[x];
                    pp.second=x;
                    H.push(pp);
                }
            }
        uz[vfmin]=1;
    }
}