#include<fstream>
#include<vector>
#include<queue>
using namespace std;

ifstream u ("dijkstra.in");
ofstream w ("dijkstra.out");

#define NMAX 50005
#define INF (1<<30)

struct muchie
{int nod, cost;
};
vector<muchie> G[NMAX];
int d[NMAX], pr[NMAX];
int nrnodes, nrarcs;

void Read()
{u>>nrnodes>>nrarcs;
 int x, y, c;
 muchie aux;

 for(int i=1; i<=nrarcs; i++)
 {
     u>>x>>y>>c;
     aux.cost=c;
     aux.nod=y;
     G[x].push_back(aux);
 }
}

class cmp
{public:
    bool operator()(const muchie &A, const muchie &B)
    {return A.cost > B.cost;
    }
};

void dijkstra(int source)
{priority_queue<muchie, vector<muchie>, cmp> q;
 int i, nextnod, nextcost;
 muchie aux;
 for(i=0; i<NMAX; i++)
    d[i]=INF;
 d[source]=0;

 aux.nod=source;
 aux.cost=0;
 q.push(aux);

 while(!q.empty())
    {muchie current=q.top();

     for(i=0; i < G[current.nod].size(); i++)
        {nextnod = G[current.nod][i].nod;
         nextcost = G[current.nod][i].cost;

         if(d[current.nod] + nextcost < d[nextnod])
            {d[nextnod] = d[current.nod] + nextcost;
             aux.cost = d[nextnod];
             aux.nod = nextnod;
             q.push(aux);
            }
        }
     q.pop();
    }
}

int main()
{Read();
 dijkstra(1);
 for(int i=2; i<=nrnodes; i++)
    if(d[i]==INF) w<<0<<" ";
 else w<<d[i]<<" ";

 return 0;
}