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

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

int n,m;
struct varf{int x,c;};
vector<varf> G[NMAX];

void dijkstra();
int start=1;
int cmin[NMAX];
int pre[NMAX];
int uz[NMAX];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

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

void dijkstra()
{
    int i,minim,vfmin,vecin,cost;
    //initializare
    for(i=1; i<=n; i++)
        cmin[i]=pre[i]=INF;
    cmin[start]=pre[start]=0;
    pq.push({0,start}); //costul 0 pana la start
    while(!pq.empty())
        {
         minim=pq.top().first;
         vfmin=pq.top().second;
         pq.pop();
         if(uz[vfmin]) continue;
         uz[vfmin]=1;
         for(i=0; i<G[vfmin].size(); i++)
            {
             vecin=G[vfmin][i].x;
             cost=G[vfmin][i].c;
             if(!uz[vecin] && cmin[vecin]>cmin[vfmin]+cost)
                {
                 cmin[vecin]=cmin[vfmin]+cost;
                 pre[vecin]=vfmin;
                 pq.push({cmin[vecin],vecin});
                }
            }
        }
}