#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct s
{
    int nod,x;
};
s heap[101];
int k=0;
vector <vector<int>>v;vector <vector<int>>cost;
s top()
{
    return heap[1];
}
void pop()
{
    heap[1]=heap[k];
    k--;
    int ok=1;
    int poz=1;
    while (ok==1 && poz<=k/2)
    {
        int minn=heap[poz*2].x;
        int o=0;
        if (heap[2*poz+1].x<minn) {minn=heap[2*poz+1].x;o=1;}
        if (heap[poz].x>minn)
        {
            s aux=heap[2*poz+o];
            heap[2*poz+o]=heap[poz];
            heap[poz]=aux;
        }
        else ok=0;
        poz=2*poz+o;
    }
}
void add(int nod,int x)
{
    heap[++k].x=x;
    heap[k].nod=nod;
    int ok=1;
    int poz=k;
    while (poz/2>=1 && ok==1)
    {
        if (heap[poz/2].x>heap[poz].x)
        {
            s aux=heap[poz/2];
            heap[poz/2]=heap[poz];
            heap[poz]=aux;
        }
        else ok=0;
        poz=poz/2;
    }
}
int viz[50001];
int d[50001];
int main()
{
 int n,m;
 fin >>n>>m;
 v.resize(n+1);
 cost.resize(n+1);
 for (int i=1;i<=m;i++)
 {
     int x,y,c;
     fin >>x>>y>>c;
     v[x].push_back(y);
     cost[x].push_back(c);
 }
 for (int i=1;i<=n;i++) d[i]=1e9;
 add(1,0);
 d[1]=0;
 while (k)
 {
     s h=top();
     int i=h.nod;
     int x=h.x;
     pop();
     if (!viz[i])
     {
         viz[i]=1;
         for (int j=0;j<v[i].size();j++)
         {
             if (d[v[i][j]]>d[i]+cost[i][j])
             {
                 d[v[i][j]]=d[i]+cost[i][j];
                 add(v[i][j],d[v[i][j]]);
             }
         }
     }
 }
for (int i=2;i<=n;i++) fout << d[i] <<" ";
}