#include<cstdio>
#include<vector>
#include<queue>
//#include<algorithm>
#define pinf (1<<30)
using namespace std;
struct noduri {int to,cost;};
vector<vector<noduri> >G(50010);
vector<int>dist;
int n,m;
void citire()
{
    freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&n,&m);
    dist.resize(n+1,pinf);
    int i,x;
    noduri aux;
    //sa pun in G sa plece de la 1
    for(i=1;i<=m;++i)
      scanf("%d%d%d",&x,&aux.to,&aux.cost), G[x].push_back(aux);
}
void dijkstra(int s)
{
    queue<int>Q;
    vector<bool>InQ(n+1,false);
    Q.push(s);
    dist[s]=0;
    InQ[s]=true;
    while(!Q.empty())
    {
        int nod=Q.front();
        Q.pop();
        InQ[nod]=false;
        for(vector<noduri>::iterator it=G[nod].begin();it!=G[nod].end();++it)
            {
                if(dist[nod]+it->cost < dist[ it->to ])
                  {
                    dist[it->to]=dist[nod]+it->cost;
                    if(!InQ[it->to])
                      Q.push(it->to),InQ[it->to]=true;
                  }

            }
    }
}
void afisare()
{
    freopen("dijkstra.out","w",stdout);
    for(vector<int>::iterator it=dist.begin()+2;it!=dist.end();++it)
       *it!=pinf ? printf("%d ",*it) : printf("0 ");
}
int main()
{
    citire();
    dijkstra(1);
    afisare();
    return 0;
}