#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<varf> G[NMAX];
int cmin[NMAX],pre[NMAX];
bool uz[NMAX];

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

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

int main()
{
    citire();

    Dijkstra();

    afisare();

    return 0;
}

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

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;

    H.push(p);

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

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

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

        if(!uz[vfmin])
        {
            for(i=0; i<G[vfmin].size(); i++){
                x=G[vfmin][i].vf;
                c=G[vfmin][i].cost;
                if(cmin[x]>cmin[vfmin]+c)
                    {cmin[x]=cmin[vfmin]+c; H.push(x);}
            }
            uz[vfmin]=1;
        }
    }
}