#include <fstream>
#include <queue>
#define NMAX 50002
#define INF 1e9

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

int n,m;

struct varf
    {
        int vf,c;
        friend bool operator < (varf a,varf b);
    };
vector<varf> G[NMAX];
int start=1;

void dijkstra(int start);
int cmin[NMAX];
int pre[NMAX];

bool operator < (varf a,varf b)
{
    return a.c > b.c;
}

priority_queue<varf> pq;

int uz[NMAX];

int main()
{
    int i,x,y,cost;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        {
        fin>>x>>y>>cost;
        G[x].push_back({y,cost});
        }
    dijkstra(start);
    for(i=2; i<=n; i++)
        if(cmin[i]==INF) fout<<0<<' ';
            else fout<<cmin[i]<<' ';
    return 0;
}

void dijkstra(int start)
{
    //initializare
    varf aux;
    int i,vecin,cost_vecin;
    for(i=1; i<=n; i++)
        {cmin[i]=INF; pre[i]=start;}
    cmin[start]=0;
    pre[start]=0;
    aux.vf=start;
    aux.c=0;
    pq.push(aux);
    while(!pq.empty())
        {
         aux=pq.top();
         pq.pop();
         if(uz[aux.vf]) continue;
         uz[aux.vf]=1;
         for(i=0; i<G[aux.vf].size(); i++)
            {
             vecin=G[aux.vf][i].vf;
             cost_vecin=G[aux.vf][i].c;
             if(cmin[vecin]>cmin[aux.vf]+cost_vecin)
                {
                 cmin[vecin]=cmin[aux.vf]+cost_vecin;
                 pq.push({vecin,cmin[vecin]});
                 pre[vecin]=aux.vf;
                }
            }
        }
}