#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
#define inf 2000000000
queue <int> q;
vector <pair<int,int> > muchii[50005];
bool inq[50005];
int dmin[50005];
int n,m,i,a,b,c,now,to,dto;
int main(void)
{
    FILE * f;
    f=fopen("dijkstra.in","r");
    ofstream g("dijkstra.out");
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        muchii[a].push_back(make_pair(b,c));
    }
    for (i=0;i<=50002;i++)
    {
        dmin[i]=inf;
        inq[i]=false;
    }
    dmin[1]=0;
    q.push(1);
    while (!q.empty())
    {
        now=q.front();
        inq[now]=false;
        for (i=0;i<int(muchii[now].size());i++)
        {
            to=muchii[now][i].first;
            dto=muchii[now][i].second;
            if (dmin[now]+dto<dmin[to])
            {
                dmin[to]=dmin[now]+dto;
                if (!inq[to])
                {
                    q.push(to);
                    inq[to]=true;
                }
            }
        }
        q.pop();
    }
    for (i=2;i<=n;i++)
        if (dmin[i]!=inf)
            g<<dmin[i]<<' ';
        else
            g<<"0 ";
    g.close();
    return 0;
}