#include <bits/stdc++.h>
#define DMAX 50010
#define INFINIT 5000000002

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct ele{int y,cost;};
vector<ele> a[DMAX];
long long int cost[DMAX];
int da[DMAX];
void citire();
int n,start,m;
void rezolva();
class compar

{
  public:
  bool operator() (const int& x, const int&y) const
  {
    return (cost[x]>cost[y]);
  }
};

int pred[DMAX];
priority_queue<int,std::vector<int>,compar> Heap;
int main()
{int i;
    citire();
    rezolva();
    for(i=2;i<=n;i++)
        if(cost[i]==INFINIT)
        fout<<0<<' ';
    else
        fout<<cost[i]<<' ';
    return 0;
}
void citire()
{
    int i,x,y,cst;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cst;
        if(y!=1)
        a[x].push_back({y,cst});
    }
    start=1;
    for(i=1;i<=n;i++)
        cost[i]=INFINIT;//pred[i]=start;
    cost[start]=0;
    //pred[start]=0;
    for(i=0;i<a[start].size();i++)
        cost[a[start][i].y]=a[start][i].cost,Heap.push(a[start][i].y),da[a[start][i].y]++;

}
void rezolva()
{int x,i;
    da[start]=1;
    while(Heap.size())
    {
        x=Heap.top();
        da[x]--;
        Heap.pop();
        if(da[x]==0)
        {for(i=0;i<a[x].size();i++)

            if(cost[x]+a[x][i].cost<cost[a[x][i].y])
        {
            cost[a[x][i].y]=cost[x]+a[x][i].cost;
            Heap.push(a[x][i].y);
            da[a[x][i].y]++;
            //pred[a[x][i].y]=x;
        }
        }


    }
}