#include <fstream>
#include <string.h>
#define dim 50001
#define INF 0x3f3f3f3f
#include <queue>
#include <vector>
#define x first
#define y second
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int d[dim],viz[dim],i,m,n,a,b,c,nod;
vector< pair<int,int> > nodes[dim];
queue <int> q;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        nodes[a].push_back(make_pair(b,c));
    }
    memset(d,INF,sizeof(d));
    d[1]=0;
    q.push(1);
    viz[1]=1;
    while(!q.empty())
    {
        nod=q.front();
        viz[nod]=0;
        for(i=0;i<nodes[nod].size();i++)
        {
            if(d[nod]+nodes[nod][i].y<d[nodes[nod][i].x])
            {
                d[nodes[nod][i].x]=d[nod]+nodes[nod][i].y;
                if(viz[nodes[nod][i].x]==0)
                {
                    viz[nodes[nod][i].x]=1;
                    q.push(nodes[nod][i].x);
                }
            }
        }
        q.pop();
    }
    for(i=2;i<=n;i++)
        if(d[i]<INF)
            fout<<d[i]<<" ";
        else
            fout<<0<<" ";
    return 0;
}