#include <fstream>
#define inf 50000001
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

struct edge
{
   int source;
   int dest;
   int weight;
} v[250001];
int d[50001];

int main()
{
    int i,n,m;
    bool ready=0;
    fin>>n>>m;
    for (i=2;i<=n;i++) d[i]=inf;
    for (i=1;i<=m;i++) fin>>v[i].source>>v[i].dest>>v[i].weight;
    while (!ready)
    {
        ready=1;
        for (i=1;i<=m;i++)
        {
            if (d[v[i].dest]>d[v[i].source]+v[i].weight)
            {
                d[v[i].dest]=d[v[i].source]+v[i].weight;
                ready=0;
            }
        }
    }
    for (i=2;i<=n;i++) {if (d[i]==inf) d[i]=-1; fout<<d[i]<<" ";}
}